基本概念

定义

对特定问题求解方法和步骤的一种描述，它是指令的有限序列。其中每个指令表示一个或多个操作。（解决问题的方法和步骤）

有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。

确定性：算法中的每一条指令必须有确切的含义，没有二义性，在任何条件下，只有唯一的一条执行路径，即对于相同的输入只能得到相同的输出。

可行性：算法是可执行的，算法描述的操作可以通过已经实现的基本操作执行有限次来实现。

输入：一个算法有零个或多个输入。

输出：一个算法有一个或多个输出。

正确性：程序对于一切合法的输入数据都能得到满足要求的结果。

可读性：便于他人阅读理解。

健壮性：对于非法输入不会产生莫名其妙的结果，处理错误的方法应该是返回错误或错误性质的值，以便在更高的抽象层次处理。

高效性：减少代码所用的时间和空间。

算法时间效率可以用依据该算法编制的程序在计算机上执行所消耗的时间来度量。

两种度量方法：

事后统计

事前分析：算法运行时间=一个简单操作所需的时间*简单操作次数

若某个辅助函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)同数量级函数。记作T(n)=O(f(n))，称O(f(n))为算法的渐进时间复杂度(O是数量级符号)

T(n)按数量级递增顺序为：常数阶----对数阶---线性阶---线性对数阶(n*log₂n)---平方阶---立方阶……k次方阶---指数阶

算法所需存储空间的度量，S(n)=O(f(n))，其中n为问题的规模（或大小）

算法要占据的空间：

算法本身要占据的空间，输入/输出，指令，常数，变量等

算法要使用的辅助空间