算法设计和算法分析基础资料文件与下载

算法设计与算法分析基础

计算机技术的每一个进步都与算法研究的突破有关。如多媒体技术的发展与数据压缩算法的研究密切相关，电子政务、电子商务、网上银行的发展离不开数据加密算法的研究。在计算机性能不断提高的同时，人类使用计算机解决的问题也在不断地变化，应用范围和规模不断增大，应用问题本身也越来越复杂。算法与计算复杂性理论表明，当问题的复杂度较高时，单纯地提高计算机性能是不能解决问题的。因此，在计算机的速度不断提高的同时，仍然需要研究算法。

一、算法的基本概念

1.算法

算法是在有限的步骤内解决数学问题的过程，是以一步接一步的方式来详细描述计算机如何将输入转化为所要求的输出的过程，即算法是对计算机上执行的计算过程的具体描述，。D.E.Knuthgei给出一个有效的算法必须满足的五个重要特性：

① 有穷性：算法必须能在有限的时间内做完，即在任何情况下，算法必须能在执行有限个步骤之后终止，都不能陷入无穷循环中。

② 确定性：算法中的每一个步骤，必须经过明确的定义，并且能够被计算机所理解和执行，而不能是抽象和模糊的概念，更不允许有二义性。

③ 输入：算法有0个或多个输入值，来描述算法开始前运算对象的初始情况，这是算法执行的起点或是依据。0个输入是指算法本身给出了运算对象的初始条件。

④ 输出：算法至少有1个或多个输出值，反映对运算对象的处理结果，没有输出的算法没有任何意义。

⑤ 可行性：算法中要做的运算都是基本运算，能够被精确地进行。即算法中执行的任何计算都可以被分解为基本的运算步，每个基本的运算步都可以在有限的时间内完成。

2.算法与算法程序

算法与计算机算法程序关系密切，但概念却不同。一个计算机程序是算法的一个具体描述，同一个算法可以用不同语言编写的程序来描述。实现算法的程序应该具备如下特性：

① 正确性：一个正确的算法程序能够实现算法问题求解的功能，即算法程序对于一切合法的输入数据都能得出正确的结果。

② 可读性：算法程序应该是易于理解的，可读性差的程序容易隐藏较多错误而难以发现。

③ 健壮性：当输入的数据非法时，算法程序应当能进行相应处理，而不是出现无法预知的输出结果。算法程序处理出错的方法不是中断程序的执行，而是应该返回一个表示错误性质的值，以便上一级程序根据错误信息进行相应处理。

二、算法分析

计算机科学就是用计算机来解决问题，它把问题作为自己的研究对象，世界是一个个需要解决的问题的集合，每一个问题又都是该问题集合中的一个实例。因此，算法的研究与实际问题直接相关，用来解一个问题可以有许多不同的算法，他们之间的效果可能会有很大差别。算法设计者最关心的就是什么是有效的算法，如何评价一个算法的优劣，如何从多种算法中选择好的算法。除了要首先考虑算法的正确性外，还要分析和评价算法的性能。分析和评价算法的性能主要要考虑以下两个方面：

① 时间代价：执行算法所耗费的时间。一个好的算法首先应该比其他算法的运行时间代价要小。算法的时间代价的大小用算法的时间复杂度来度量。

② 空间代价：执行算法所耗费的存储空间，主要是辅助空间。算法运行所需的空间消耗是衡量算法优劣的另一个重要因素。算法的空间代价的大小用算法的空间复杂度来度量。

算法的性能评价是指算法程序在计算机上运行，测量它所耗费的时间和存储空间。由于运行算法程序的计算机的性能的差别以及软件平台和描述语言的差别，无法用算法的实际时间消耗和空间消耗来度量算法的时间复杂度和空间复杂度。所以，算法的性能分析就是指对算法的时间复杂度和空间复杂度进行事前估计，与具体的计算机、软件平台、程序语言和编译器无关。

提示：由于面对自然界和人类社会的各种问题，计算速度的挑战是第一位的。所以，算法的时间复杂度的分析常常比空间复杂度分析要重要。在许多应用问题中，往往会适当地增加空间代价来减少时间代价，例如本书将要介绍的动态规划策略就是一种以空间换时间的算法设计策略。

1.时间复杂度

一个算法所耗费的时间，应是该算法中每条语句的执行时间之和，而每条语句的执行时间就是该语句的执行次数（也称频度）与该语句执行一次所需时间的乘积。一个算法的时间耗费就是该算法中所有语句的频度之和。

由于算法时间复杂度的度量不依赖于算法程序运行的软硬件平台，统一的方法是用执行的基本操作的次数来度量算法时间复杂度。算法运行的时间代价和空间代价都与问题的规模有关。

① 基本操作

基本操作是指算法运行中起主要作用且花费最多时间的操作。对于基本操作的概念没有精确定义。在实际算法分析时，可以自由决定算法运行的基本操作。例如：在比较排序算法的分析中，基本操作可以是数据之间的比较操作，也可以是数据元素的移动操作，还可以是比较和移动的次数之和。

② 问题规模

问题规模是指该问题的一个实例的输入规模的大小。同样，问题规模的概念也没有精确定义，根据问题的不同而不同。例如：对于排序问题，问题实际长度是待排序元素序列的长度n。

因此，一个算法的时间复杂度可由问题规模的函数来表示，即一个算法的时间代价是由该算法用于问题规模为n的实例所需的基本操作次数来确定。一般用T(n)来表示算法的基本计算次数，亦即算法的时间复杂度。

【例1】分析两个n阶矩阵相乘C=A×B，所需要的基本运算次数T(n)。

用C++描述的算法如下：

for(i=0; i<n; i++) //运算n+1次

for(j=0; j<n; j++) //运算n(n+1)次

{

c[i][j]=0; //运算n²次

for(k=0; k<n; k++) //运算n²(n+1)次

c[i][j]=c[i][j]+a[i][k]*b[k][j]; //运算n³次

}

分析两个n阶矩阵相乘的算法可知，外层循环的控制变量i从0增加到n时，循环才会终止，故其运算次数为n+1；第二层循环，是外循环的循环体，应该运算n次，而第二层循环本身要运算n+1次，故第二层循环的运算次数为n(n+1)，语句c[i][j]=0的运算次数为n²；内循环又是第二层循环的循环体，应该运算n² 次，而内循环本身要运算n+1次，故内循环的运算次数是n²(n+1)，语句c[i][j]=c[i][j]+a[i][k]*b[k][j]的运算次数为n³。因此，该算法所有语句的运算次数之和T(n)=2n³+3n²+2n+1。

在算法分析时，一般采用大O表示法：一般来说，计算机算法的时间复杂度是问题规模n的函数f(n)，如果存在正的常数c和n₀，当问题的规模n≥n₀后，算法的时间（或空间）复杂度T(n)≤c·f(n)，则该算法的时间（或空间）复杂度为O(f(n))，记为:

                                               T(n)= O (f(n))

对于比较复杂的程序，往往无法精确地计算算法的复杂度，因此一般是根据复杂度函数的渐近性质来比较算法优劣。当问题的规模n趋向无穷大时，时间复杂度T(n)的量级（阶）称为算法渐近时间复杂度，简称时间复杂度。在例1-1中，当n趋于无穷大时，T(n)与n³之比是一个不等于零的常数，T(n)/n³ →2  （当n → ∞ 时），则T(n)和n³是同阶的。所以，两个n阶矩阵相乘算法的时间复杂度T(n)的量级为O(n³)，记为：

                                                                                       T(n)=O(n³)

时间复杂度T(n)的量级，实际上是由f(n)的高次项决定的。因此，在具体分析算法的时间复杂度时，可采用如下方法：

l 一般可只考虑与程序规模有关的运行次数最多的语句，如循环语句的循环体、多重循环中的内循环等。

l 若语句很少执行且与规模n无关，则可忽略不计。

l 若所有语句都与规模n无关，则即使有上千条语句，其执行时间也仅仅是一个较大的常数，故时间复杂度的量级是O (n0)= O (1)。

l 对于较复杂的算法，我们可以将它分成几个容易估算的部分，然后利用量级加法规则或乘法规则计算整个算法的时间复杂度。

加法规则

若算法的两部分的时间复杂度分别为：T₁(n)= O (f₁(n))和T₂(n)= O (f₂(n))，且这两部分是顺序执行的，则算法的时间复杂度T(n)为：

                                                                 T(n)=T₁(n)+T₂(n)=O (max (f₁(n), f₂(n)))。

乘法规则

若算法的两部分的时间复杂度为：T₁(n)= O (f₁(n))和T₂(n)= O (f₂(n))，如果第一部分的时间代价T₁(n)= O (f₁(n))的时间单位不是最基本的，而是以第二部分的时间代价T₂(n)= O (f₂(n))为基础来考虑的，则算法的时间复杂度T(n)为：

                                                                T(n)=T₁(n)×T₂(n)=O (f₁(n)×f₂(n))

按数量级递增排列，常见的时间复杂度有：常数阶O(1)、对数阶O(log₂n)、线性阶O(n)、线性对数阶O(nlog₂n)、平方阶O(n²)、立方阶O(n³)、......。

提示：一般情况下，讨论算法的时间复杂度时，没有必要精确计算出算法的执行次数（即频度），只要计算出算法时间复杂度的量级就可以了。通常认为，具有指数阶量级的算法是实际不可计算的，而量级低于平方阶的算法是高效率的。

【例2】分析下面程序段的时间复杂度。

//交换a和b的内容

t=a;

a=b;

b=a;

分析：三条语句的执行次数均为1，与规模n无关，故可知其时间复杂度为O(1)。

【例3】分析下面程序段的时间复杂度。

//求n以内所有2的幂次数的和，即1+2¹+2²+…+2^k，2^k≤n

sum=0;

for (i=1; i<=n; i*=2)  sum+=i;

分析：执行次数最多的语句是循环体sum+=i，它执行的次数与n有关，但不是n次，若设为m次，由于2^m≤n，所以有m≤log₂n，故时间复杂度为O(log₂n)。

【例4】分析下面程序段的时间复杂度。

//给二维数组a[][]赋值i+j

for (i=0; i<n; i++)

for (j=0; j<n; j++)

a[i][j]=i+j;

分析：执行次数最多的语句是内循环的循环体a[i][j]=i+j，该语句执行了n²次，所以时间复杂度为O(n²)。

在具体分析一个算法的时间复杂度时，还会存在这样的问题：对于规模为n的问题，算法所执行的基本运算次数还可能与特定的输入有关，但又不可能将算法所有可能的基本运算次数都列举出来。例如：在长度为n的一维数组中，查找值为x的元素，若采用顺序查找算法，即从数组的第一个元素开始，逐个与被查找值x进行比较。显然，如果第一个元素值恰好等于x，则只需比较一次，就得到结果；如果最后一个元素值等于x，或所有元素的值都不等于x，则需要比较n次，才能得到结果。因此，在这个问题的算法中，其基本运算（即比较）的次数与具体的被查找（输入）值x有关。

由于算法的复杂度常常与输入有关，所以通常采用平均时间复杂度和最坏时间复杂度来衡量一个算法的复杂度。

（1）平均时间复杂度

平均时间复杂度是指在问题规模为n时，用各种特定输入条件下的基本运算次数的加权平均值来衡量算法的复杂度。

设x是所有可能输入中的某个特定输入，p(x)是x出现的概率（即输入为x的概率），t(x)是算法在输入为x时所执行的基本运算次数，则算法的平均运算次数为：

其中，D_n表示当问题规模为n时，算法所有可能的输入组成的集合。通过分析算法可以确定上式中的t(x)。上式中的p(x)需要根据经验或用算法中有关的一些特定信息来确定。若p(x)比较难确定，则分析算法的平均时间复杂度也会较困难。

（2）最坏时间复杂度

最坏时间复杂度是指在问题规模为n时，用算法所执行的基本运算的最大次数来衡量算法的时间复杂度。

设x是所有可能输入中的某个特定输入，t(x)是算法在输入为x时所执行的基本运算次数，则算法最多的运算次数为：

显然，W(n)的计算要比A(n)的计算方便得多。由于最坏时间复杂度给出了算法时间复杂度的一个上界，即对于任何输入，算法的时间复杂度都不会大于W(n)。因此，最坏时间复杂度往往比平均时间复杂度更具有参考价值。

提示：如果不特别说明，当某个算法的时间复杂度为T(n)时，指的就是其最坏时间复杂度，即T(n)=W(n)。由于最好时间复杂度的意义不大，因此一般不进行最好时间复杂度的分析。

2 空间复杂度

算法的空间复杂度是指算法在计算机内执行时所需存储空间的度量。一般来说，计算机算法的空间复杂度也是问题规模n的函数f(n)，算法的空间复杂度记为:

                                                                        S(n)= O (f(n))

同时间复杂度相比，空间复杂度的分析要简单得多。其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。今后若无特别说明，就将算法的空间复杂度量级，近似地看作算法的空间复杂度。

一个程序所占用的存储空间，由以下几部分构成：

① 指令空间：是指用来存储经过编译后的程序指令所需要的存储空间。程序所需的指令空间与所使用的编译器、所设置的编译器选项以及目标计算机等因素有关。

② 数据空间：是指程序中数据所占的存储空间。数据空间包括常量和简单变量所占据的空间，以及存储数据结构所需的空间和通过动态分配申请到的空间。

③ 环境栈空间：用来保存函数调用返回时所需的信息。

可将上述程序所需的存储空间划分为两部分：

① 固定部分：是指与问题实例特性无关的那部分空间。如指令空间，数据空间中常量、简单变量和结构或对象的定长成员变量所占的空间。

② 变化部分：是指依赖于问题实例特性的那部分空间。如与实际问题实例规模有关的输入输出和中间处理所需的空间，以及递归栈空间等。

程序所需的空间由多种因素决定，有些因素与编译器和程序运行的计算机有关。所以，在进行算法的空间复杂度分析时，一般主要考虑依赖于问题特征、决定问题规模的那些因素——实例特性。

在具体分析算法的空间复杂度时，可采用如下方法：

l 若输入数据所占空间只与问题有关，和算法无关，则只需要分析除输入和程序之外需要的额外空间。

l 若额外空间量相对于问题规模来说是常数，则称该算法是原地工作的。

l 若所需存储量依赖于特定的输入，则通常按最坏情况考虑。

【例5】下面的函数模板Sum的功能是计算数组元素的和，分析该算法的空间复杂度。

template<class T>

T Sum(T a[],int n)  //计算数组a所有元素的和

{

T sum=0；

for (int i=0;i<n;i++)

sum+=a[i];

return sum;

}

空间复杂度分析：

对于Sum函数，设数组a的元素个数为n，即此问题的规模为n。Sum函数只需要给参数a、n，及函数体中声明的变量i和sum分配存储空间。由于算法所需的空间与规模n无关，所以，S(n) = O(1)。

【例6】下面的函数模板Rsum的功能是用递归法计算数组元素的和，分析它的空间复杂度。

template<class T>

T Rsum(T a[],int n)  //计算数组a所有元素的和

{

if (n>0)

return Rsum(a,n-1)+a[n-1];

else

return 0;

}

空间复杂度分析：

对于Rsum函数，设数组a的元素个数为n，即此问题的规模为n。采用递归算法，递归栈空间需要存储参数a和参数n及返回地址等信息。对于参数a，需要存储一个指针，假设4个字节。对于参数n需要分配一个int型的空间，假设4个字节。如果返回地址也占4个字节，这样每调用一次Rsum函数需要12个字节的空间，由于递归深度为n+1，共需要12(n+1)字节的递归栈空间，所以，S(n) = 12(n+1) = O(n)。

三、算法分析实例

1.多项式求值问题

【例7】多项式，当n次项不为零时，P(x)是一个n次多项式。下面的代码是计算对于给定的x，多项式P(x)的值。其中，coeff存储多项式的系数。

template<class T>

T PolyEval(T coeff[], int n, const T& x)

{

T y=1,value=coeff[0]；

for (int i=1;i<=n;i++)

{

y*=x;

value+=y*coeff[i];

}

return value;

}

（1）时间复杂度分析

对于上面的代码，可以根据for循环内部所执行的加法和乘法次数来估计时间复杂度。假设n表示问题的规模，由于进入for循环的总次数为n，每次循环执行2次乘法和一次加法（不包括循环控制变量i每次递增所执行的加法），即加法的次数为n，乘法的次数为2n。所以，T(n) = O(n)。

（2）空间复杂度分析

对于PolyEval函数而言，只需要存储参数coeff和n以及变量i、y和value，即算法的空间复杂度S(n)=O(1)。可见，多项式求值算法的输入数据所占空间只与问题规模有关，和算法无关。所以，只需要分析除数据空间和指令空间之外的环境栈空间。该函数不是递归函数，调用该函数所需的环境栈空间也是常数。因此，实现多项式求值需要的存储空间可用存储问题数据（系数）的空间来近似，即空间复杂度为O(ns)，其中，s是每个数据元素（系数）空间的大小。

2. 静态查找问题

【例8】下面代码是顺序查找算法，从数组a的第一个元素开始，逐个与被查找值 x 进行比较。如果找到一个元素与x相等，则函数返回第一次出现x的数组下标。如果在数组中没有找到这个元素，函数返回-1。分析顺序查找法在长度为n的一维数组中查找值为x的元素平均时间复杂度、最坏时间复杂度和空间复杂度。

template<class T>

int SeqSearch(T a[],int n,constT& x)

{

for (int i=0;i<n;i++)

if (a[i]==x)

return i;

return -1;

}

（1）时间复杂度分析

当需要查找的x为数组中第i个元素时，则在查找过程中，需要i次比较；当需要查找的x不在数组中时，则需要进行n次比较。即比较次数为：

其中，i=n+1表示x不在数组中的情况。

假设被查找项x在数组中出现的概率为q，且要查找的x出现在数组中每个位置上的可能性一样，则 x 出现在数组中每一个位置上的概率为q/n，而x不在数组中的概率为1-q 。即：

其中，i=n+1表示x不在数组中的情况。

因此，用顺序搜索法在长度为n的一维数组中查找值为x的元素，平均需要进行的比较次数为：

如果已知需要查找的x一定在数组中，即q=1，则：

在这种情况下，用顺序搜索法在长度为n的一维数组中查找值为x的元素，平均情况下需要检查数组中一半的元素。

如果已知需要查找的x有一半的机会在数组中，即q=1/2，则：

在这种情况下，用顺序搜索法在长度为 n 的一维数组中查找值为x的元素，平均情况下需要检查数组中3/4的元素。

最坏情况发生在需要查找的x是数组中的最后一个元素，或x不在数组中的时候，此时：

可见，顺序查找算法的时间复杂度在平均情况和最坏情况下均为O(n)。

（2）空间复杂度分析

对于SeqSearch函数而言，只需要存储参数a和n以及变量i，即算法的空间复杂度S(n)=O(1)。可见，顺序查找算法的输入数据所占空间只与问题规模有关，和算法无关。所以，只需要分析除数据空间和指令空间之外的环境栈空间。调用该函数所需的环境栈空间也是常数。因此，实现顺序查找算法需要的存储空间可用存储问题数据的空间来近似，即空间复杂度为O(ns)，其中，s是每个数据元素空间的大小。

提示：例7的算法复杂度与具体输入有关，A(n)只是它的加权平均值，此时，A(n)会小于等于W(n)。在另外一些情况下，算法的计算工作量与输入无关，即当规模为n时，在所有可能的输入下，算法所执行的基本运算次数是一定的，此时有A(n)=W(n)，如例6。再例如，两个 n 阶的矩阵相乘，都需要做n³次实数乘法，而与输入矩阵的具体元素无关。