下载掌阅APP，畅读海量书库
立即打开
算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每条指令表示一个或多个操作。一个算法具有以下5个重要的特性。
一个算法必须总是在执行有穷步（对任何合法的输入值）之后，且每一步都可在有穷时间内完成。即一个算法对于任意一组合法输入值，在执行有穷步之后一定能够结束。
算法中每一条指令都必须有确切的含义，使读者在理解时不会产生二义性。同时，在任何条件下，算法都只有一条执行路径，即对于相同的输入只能得出相同的结果。
算法中所描述的操作必须足够基本，且都可以通过已经实现的基本操作执行有限次来实现。
作为算法加工对象的量值，一个算法有0个或多个输入。有的量值需要在算法执行过程中输入，而有的算法表面上没有输入，实际上已经被嵌入算法中。
输出是一组同“输入”有确定对应关系的量值，是算法进行信息加工后所得到的产物，一个算法可以有一个或多个输出。
设计一个算法时，它应该满足以下4个要求。
（1）正确性
要求算法能够正确地实现预先规定的功能和满足性能要求，这是最重要也是最基本的标准。目前大多数算法是用自然语言描述需求的，它至少应包括输入、输出和加工处理等的明确无歧义的描述。设计或选择算法应当能正确地反映这种需求。
（2）可读性
算法应当易于理解，可读性强。为了达到这个要求，算法必须做到逻辑清晰、简单并且结构化。晦涩难懂的程序容易隐藏较多错误，难以调试和修改。
（3）健壮性
算法要求具有良好的容错性，能够提供异常处理，能够对输入进行检查。不经常产生异常中断或死机现象。例如，一个求矩形面积的算法，当输入的坐标集合不能构成一个矩形时，不应继续计算，而应当报告输入错误。同时，处理错误的方法是返回一个表示错误的值，而不是输出错误信息或直接异常中断。
（4）效率与低存储量要求
通常算法的效率主要指算法的执行时间。对于同一个问题，如果能用多种算法进行求解，执行时间短的算法效率高。算法存储量指的是算法执行过程中所需的存储空间。效率与低存储量要求这两者都与问题的规模有关。例如，求100个学生的平均成绩和求10000个学生的平均成绩在时间和空间的成本上必然是存在差异的。
一个算法用高级语言实现以后，在计算机上运行时所消耗的时间与很多因素有关，主要因素列举如下。
①依据算法所选择的具体策略。
②问题的规模，如求100以内还是1000以内的素数。
③编写程序的语言，对于同一个算法，实现语言的级别越高，执行效率往往越低。
④编译程序所产生的计算机代码的质量。
⑤计算机执行指令的速度。
很显然，一个算法用不同的策略实现，或用不同的语言实现，或在不同的计算机上执行，它所耗费的时间是不一样的，因而效率均不相同。由此可知，使用一个绝对的时间单位去衡量一个算法的效率是不准确的。在上述5个因素当中，最后3个均与具体的计算机有关，抛开这些与计算机硬件、软件有关的因素，仅考虑算法本身的效率，可以认为一个特定算法的“执行工作量”只依赖于问题的规模，换而言之是问题的规模的函数。
一个算法是由控制结构（顺序、分支和循环）和原操作（指固有数据类型的操作）构成的，算法的执行时间取决于二者的综合结果。为了便于比较同一问题的不同算法，通常从算法中选取一种对于所研究的问题来说是基本运算的原操作，算法执行的时间大致为基本运算所需的时间与其运行次数（一条语句的运行次数称为语句频度）的乘积。
微课1-3 算法效率的评价
显然，在一个算法中，执行的基本运算次数越少，其执行时间就相对越少；执行基本运算的次数越多，其运行时间也相对越多。换言之，一个算法的执行时间可以看成基本运算执行的次数。
算法基本运算次数 T ( n )是问题规模 n 的某个函数 f ( n )，记作
T ( n )= O ( f ( n ))
其中，记号“ O ”读作“大欧”（值数量级），它表示随问题规模 n 的增大，算法执行时间的增长和 f ( n )的增长率相同，称为算法的时间复杂度。
“ O ”的形式定义为：若 f(n) 是正整数 n 的一个函数，则 T ( n )= O ( f ( n ))表示存在一个正的常数 M ，使得当 n ≥ n 0 时都满足| T ( n )|≤ M | f ( n )|，也就是只求出 T ( n )的最高阶，忽略其低阶项和常数，这样既可以简化计算，又可以较为客观地反映当 n 很大时算法的效率。
一个没有循环的算法中基本运算次数与问题规模 n 无关，记为 O (1)，也称作常数阶。一个只有一重循环的算法中基本次数与问题规模 n 的增长呈线性增大关系，记为 O ( n )，也称线性阶。例如，以下3个程序段：
（a）{ ++ x; s = 0; }
（b）for(i = 1; i <= n; i ++ ){ ++ x; s += x; }
（c）for(j = 1; j <= n; j ++ )
for(k = 1; k <= n; k ++) { ++ x; s += x; }
含基本操作“++x”的语句频度分别为1、 n 和 n 2 ，则这3个程序段的时间复杂度分别为 O (1)、 O ( n )和 O ( n 2 )，分别称为常量阶、线性阶和平方阶。各种不同数量级对应的值存在如下关系：
O (1)< O (log 2 n )< O ( n )< O ( n log 2 n )< O ( n 2 )< O ( n 3 )< O (2 n )< O ( n !)
例1-4 分析以下算法的时间复杂度。
void fun(int a[],int n,int k)
{
int i;
i = 0; //语句（1）
while(i < n && a[i] != k) //语句（2）
i ++; //语句（3）
return (i); //语句（4）
}
解 该算法完成在一维数组 a [ n ]中查找给定值 k 的功能。语句（3）的频度不仅与问题规模 n 有关，还与输入实例中 a 的各个元素取值是否等于 k 的取值有关，即与输入实例的初始状态有关。若 a 中没有与 k 相等的元素，则语句（3）的频度为 n ；若 a 中的第一个元素 a [0]等于 k ，则语句（3）的频度是常数0。在这种情况下，可用最坏情况下的时间复杂度作为算法的时间复杂度。这样做的原因是，最坏情况下的时间复杂度是在任何输入实例里运行时间的上界。
有时也可以选择以算法的平均时间复杂度作为讨论目标。所谓平均时间复杂度，是指所有可能的输入实例在以等概率出现的情况下算法的期望运行时间与问题规模 n 的数量级的关系。例1-4中， k 出现在任何位置的概率相同，都为1/ n ，则语句（3）的平均时间复杂度为
(0+1+2+…+( n −1))/ n = ( n −1)/2
它决定此程序的平均时间复杂度的数量级为 O ( n )。
例1-5 分析以下算法的时间复杂度。
float RSum(float list[],int n)
{
count ++;
if(n){
count ++;
return RSum(list,n-1) + list[n-1];
}
count ++;
return 0;
}
解 例1-5是求数组元素之和的递归程序。为了确定这一递归程序的程序步，首先考虑当 n =0时的情况。显然，当 n =0时，程序只执行if条件判断语句和第二条return语句，所需程序步数为2。当 n >0时，程序在执行if条件判断语句后，将执行第一条return语句。此return语句不是简单返回，而是在调用函数RSum(list, n −1)后，再执行一次加法运算后返回。
设RSum(list, n )的程序步为 T ( n )，则RSum(list, n −1)为 T ( n −1)，那么，当 n >0时， T ( n )= T ( n −1)+2。于是有
这是一个递推关系式，它可以通过转换成如下公式来计算
根据上述结果可知，该程序的时间复杂度为线性阶，即 O ( n )。
一个算法的空间复杂度是指算法运行所需的存储空间。算法运行所需的存储空间包括如下两个部分。
这部分空间域所处理数据的规模大小和个数无关，换言之，与问题实例的特征无关，主要包括程序代码、常量、简单变量、定长成分的结构变量所占的空间。
这部分空间大小与算法在某次执行中处理的特定数据的规模有关。例如，分别包含100个元素的两个数组相加，与分别包含10个元素的两个数组相加，所需的存储空间显然是不同的。这部分存储空间包括数据元素所占的空间，以及算法执行所需的额外空间，例如，运行递归算法所需的系统栈空间。
在对算法进行存储空间分析时，只考察辅助变量所占空间，所以空间复杂度是对一个算法在运行过程中临时占用的存储空间大小的度量，一般也作为问题规模 n 的函数，以数量级的形式给出，记作
S ( n )= O ( g ( n ))
若所需额外空间相对于输入数据量来说是常数，则称此算法为原地工作或就地工作；若所需存储空间依赖特定的输入，则通常按最坏情况考虑。
例1-6 分析例1-4算法的空间复杂度。
解 对于例1-4的算法，只定义了一个辅助变量 i ，临时存储空间大小与问题规模 n 无关，所以空间复杂度为 O (1)。
例1-7 有如下算法，求其空间复杂度。
void fun(int a[],int n,int k)
{
int i;
if(k == n - 1) {
for(i = 0;i < n;i ++)
System.out.println(a[i]);
}
else
{
for(i = k;i < n;i ++)
a[i] = a[i] + i * i;
fun(a,n,k+1);
}
}
设fun(a, n, k)的临时空间大小为 S ( k )，其中定义了一个辅助变量 k ，并有
计算fun(a, n, 0)所需的空间为 S (0)，则
