算法的概述

1.算法和数据结构

1.1. 算法

在计算机领域，算法是一系列程序指令，用于处理特定的运算和逻辑的问题。 算

法中的指令描述的是一个计算，当其运行时能从一个初始状态和（可能为空的）初始输入开始，经过一系列有限而清晰定义的状态，最终产生输出并停止于一个终态。一个状态到另一个状态的转移不一定是确定的。随机化算法在内的一些算法，包含了一些随机输入。

特征：一个算法应该具有以下五个重要的特征：

有穷性（Finiteness）

算法的有穷性是指算法必须能在执行有限个步骤之后终止；

确切性(Definiteness)

算法的每一步骤必须有确切的定义；

输入项(Input)

一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件
；

输出项(Output)

一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；

可行性(Effectiveness)

算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步骤，即每个计算步骤都可以在有限时间内完成（也称之为有效性）。

常见的算法：

递推法、递归法、穷举法、贪心算法、分治法、动态规划法、迭代法、分支界限法、回溯法

1.2数据结构

数据结构是数据的组织、管理和储存格式，其使用目的是为了高效的访问和修改数据。 常见数据结构有：数组、链表这个样的线性数据结构，也包含树、图这样复杂结构。 

运算的具体实现要在储存结构上进行。一般有以下几种常用运算： 

(1)检索。检索就是在数据结构里查找满足一定条件的节点。一般是给定一个某字段的值，找具有该字段值的节点。 

(2)插入。往数据结构中增加新的节点。 

(3)删除。把指定的结点从数据结构中去掉。 

(4)更新。改变指定节点的一个或多个字段的值。 

(5)排序。把节点按某种指定的顺序重新排列。例如递增或递减。 

分类

数据结构有很多种，一般来说，按照数据的逻辑结构对其简单分类，包含线性结构和非线性结构两类。 

线性结构

简单地说，线性结构就是表中各个结点具有线性关系。如果从数据结构的语言来描述，线性结构应该包括如下几点： 

1、线性结构是非空集。 

2、线性结构有且仅有一个开始结点和一个终端结点。 

3、线性结构所有结点都最多只有一个直接前驱结点和一个直接后继结点。 

线性表就是典型的线性结构，还有栈、队列和串等都属于线性结构。 

非线性结构

简单地说，非线性结构就是表中各个结点之间具有多个对应关系。如果从数据结构的语言来描述，非线性结构应该包括如下几点： 

1、非线性结构是非空集。 

2、非线性结构的一个结点可能有多个直接前驱结点和多个直接后继结点。 

在实际应用中，数组、广义表、和图结构等数据结构都属于非线性结构。 

2.时间复杂度

时间复杂度是对一个算法运行时间长短的度量，用大O表示，记作T（n） = O(f（n）)。我们常见的时间复杂度按照从低到高排序是，O(1) <  O(logn)  <  O(n)  < O(nlogn) < O() 

3.空间复杂度

空间复杂度是对一个算法在运算过程中临时占有储存空间大小的度量，记作 S（n） = O(f（n）) 

常见的空间复杂度按照从低到高排序是，O(1) < O(n)  < O()。