算法和算法评价

算法的基本概念

算法（Algorithm）是对特定问题求解步骤的一种描述，它是指令的有限序列，其中的每条指令表示一个或多个操作。此外，一个算法还具有下列 5 个重要特性：

1. 有穷性。一个算法必须总在执行有穷步之后结束，且每一步都可在有穷时间内完成。
2. 确定性。算法中每条指令必须有确切的含义，对于相同的输入只能得出相同的输出。
3. 可行性。算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。
4. 输入。一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合。
5. 输出。一个算法有一个或多个输出，这些输出是与输入有着某种特定关系的量。

通常，设计一个“好”的算法应考虑达到以下目标：

1. 正确性。算法应能够正确地解决求解问题。
2. 可读性。算法应具有良好的可读性，以帮助人们理解。
3. 健壮性。输入非法数据时，算法能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果。
4. 效率与低存储量需求。效率是指算法执行的时间，存储量需求是指算法执行过程中所需要的最大存储空间，这两者都与问题的规模有关。

算法效率的度量

算法效率的度量是通过时间复杂度和 空间复杂度来描述的。

时间复杂度

一个语句的频度是指该语句在算法中被重复执行的次数。算法中所有语句的频度之和记为 #card=math&code=T%28n%29&id=tKGue) ，它是该算法问题规模 的函数，时间复杂度主要分析 #card=math&code=T%28n%29&id=OdMsX) 的数量级。算法中基本运算（最深层循环内的语句）的频度与 #card=math&code=T%28n%29&id=Q5HbQ) 同数量级，因此通常采用算法中基本运算的频度 #card=math&code=f%28n%29&id=aLpWW) 来分析算法的时间复杂度。取 #card=math&code=f%28n%29&id=d9J2t) 中随 增长最快的项，将其系数置为 1 作为时间复杂度的度量。例如， 的时间复杂度为 。 因此，算法的时间复杂度记为:

式中，的含义是#card=math&code=T%28n%29&id=WXhzm)的数量级，其严格的数学定义是：若 #card=math&code=T%28n%29&id=QJ57v) 和 #card=math&code=f%28n%29&id=nv9NK) 是定义在正整数集合上的两个函数，则存在正常数 和 ,使得当 时，都满足 %20%5Cle%20Cf(n)#card=math&code=0%20%5Cle%20T%28n%29%20%5Cle%20Cf%28n%29&id=vgvLj) 。

算法的时间复杂度不仅依赖于问题的规模 ,也取决于待输入数据的性质（如输入数据元素的初始状态）。例如，在数组A[0...n-1]中，查找给定值 k 的算法大致如下：

1. i = n-1;
2. while(i>=0&&(A[i]!=k))
3. i--
4. return i;

该算法中语句 3（基本运算）的频度不仅与问题规模 有关，而且与输入实例中A的各元素的取值及k的取值有关：

• 若A中没有与k相等的元素，则语句 3 的频度 %3Dn#card=math&code=f%28n%29%3Dn&id=omtpR)。

• 若 A 的最后一个元素等于 k，则语句 3 的频度 #card=math&code=f%28n%29&id=G5n6T) 是常数 0。

• 最坏时间复杂度是指在最坏情况下，算法的时间复杂度。

• 平均时间复杂度是指所有可能输入实例在等概率出现的情况下，算法的期望运行时间。
• 最好时间复杂度是指在最好情况下，算法的时间复杂度。

一般总是考虑在最坏情况下的时间复杂度，以保证算法的运行时间不会比它更长。在分析一个程序的时间复杂性时，有以下两条规则：

1. 加法规则：
2. 乘法规则：

常见的渐进时间复杂度为 ：

空间复杂度

算法的空间复杂度 #card=math&code=S%28n%29&id=l4W7e) 定义为该算法所耗费的储存空间，它是问题规模 的函数。记为： 一个程序在执行时除需要储存空间来存放本身所用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间。若输入数据所占空间只取决于问题本身，和算法无关，则只需分析除输入和程序之外的额外空间。

算法原地工作是指算法所需的辅助空间为常量，即 #card=math&code=O%281%29&id=onNgj) 。