算法复杂度分析

1、1、算法复杂度的分析方法及其运用算法复杂度是在数据结构这门课程的第一章里出现的，因为它稍微涉及到一些数学问题，所以很多同学感觉很难，加上这个概念也不是那么具体，更让许多同学复习起来无从下手，下面我们就这个问题给各位考生进行分析。首先了解一下几个概念。一个是时间复杂度，一个是渐近时间复杂度。前者是某个算法的时间耗费，它是该算法所求解问题规模n的函数，而后者是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。当我们评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度，因此，在算法分析时，往往对两者不予区分，经常是将渐近时间复杂度T(n)=O(f(n)简称为时间复杂度，其中的f(n)一般是算

2、法中频度最大的语句频度。此外，算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。但是我们总是考虑在最坏的情况下的时间复杂度。以保证算法的运行时间不会比它更长。常见的时间复杂度，按数量级递增排列依次为：常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n2)、立方阶O(n3)、k次方阶O(nk)、指数阶O(2n)。下面我们通过例子加以说明，让大家碰到问题时知道如何去解决。1、设三个函数f,g,h分别为 f(n)=100n3+n2+1000 , g(n)=25n3+5000n2 , h(n)=n1.5+5000nlgn请判断下列关系是

3、否成立：（1） f(n)=O(g(n)（2） g(n)=O(f(n)（3） h(n)=O(n1.5)（4） h(n)=O(nlgn)这里我们复习一下渐近时间复杂度的表示法T(n)=O(f(n)，这里的O是数学符号，它的严格定义是若T(n)和f(n)是定义在正整数集合上的两个函数，则T(n)=O(f(n)表示存在正的常数C和n0 ,使得当nn0时都满足0T(n)C?f(n)。用容易理解的话说就是这两个函数当整型自变量n趋向于无穷大时，两者的比值是一个不等于0的常数。这么一来，就好计算了吧。 (1)成立。题中由于两个函数的最高次项都是n3,因此当n时，两个函数的比值是一个常数，所以这个关系式是成立

4、的。 （2）成立。与上同理。 （3）成立。与上同理。 （4）不成立。由于当n时n1.5比nlgn递增的快，所以h(n)与nlgn的比值不是常数，故不成立。2、设n为正整数，利用大O记号，将下列程序段的执行时间表示为n的函数。(1) i=1; k=0while(i1while (x=(y+1)*(y+1)y+;解答：T(n)=n1/2 ，T(n)=O(n1/2)， 最坏的情况是y=0，那么循环的次数是n1/2次，这是一个按平方根阶递增的函数。(3) x=91; y=100;while(y0)if(x100)x=x-10;y-;else x+;解答： T(n)=O(1)， 这个程序看起来有点吓人，

5、总共循环运行了1000次，但是我们看到n没有? 没。这段程序的运行是和n无关的，就算它再循环一万年，我们也不管他，只是一个常数阶的函数2、算法复杂度编辑算法复杂度，即算法在编写成可执行程序后，运行时所需要的资源，资源包括时间资源和内存资源。中文名算法复杂度影响效率分类时间复杂度和空间复杂度关键输入量相关时间复杂度应用数学目录1简介2时间复杂度3空间复杂度4复杂度分析1简介编辑同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。2时间复杂度编辑（1）时间频度一个算法执行所耗费的时间，

6、从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。算法的时间复杂度是指执行算法所需要的计算工作量。（2）时间复杂度在刚才提到的时间频度中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T

7、(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n),称O(f(n) 为算法的渐进时间复杂度，简称时间复杂度。在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为O(1),另外，在时间频度不相同时，时间复杂度有可能相同，如T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同，但时间复杂度相同，都为O(n2)。按数量级递增排列，常见的时间复杂度有：常数阶O(1),对数阶O(log2n)(以2为底n的对数，下同),线性阶O(n),线性对数阶O(nlog2n

8、),平方阶O(n2)，立方阶O(n3),.，k次方阶O(nk),指数阶O(2n)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。算法的时间性能分析（1）算法耗费的时间和语句频度一个算法所耗费的时间=算法中每条语句的执行时间之和每条语句的执行时间=语句的执行次数(即频度(Frequency Count)语句执行一次所需时间算法转换为程序后，每条语句执行一次所需的时间取决于机器的指令性能、速度以及编译所产生的代码质量等难以确定的因素。若要独立于机器的软、硬件系统来分析算法的时间耗费，则设每条语句执行一次所需的时间均是单位时间，一个算法的时间耗费就是该算法中所有语句的频度之和

9、。求两个n阶方阵的乘积 C=AB,其算法如下:# define n 100 / n 可根据需要定义,这里假定为100void MatrixMultiply(int Aa，int B nn，int Cnn) /右边列为各语句的频度int i ,j ,k;(1) for(i=0; in;i+) n+1(2) for (j=0;jn;j+) n(n+1)(3) Cij=0; n2(4) for (k=0; kn; k+) n2(n+1)(5) Cij=Cij+Aik*Bkj;n3该算法中所有语句的频度之和(即算法的时间耗费)为：T(n)=2n3+3n2+2n+1 (1.1)分析：语句(1)的循环控制

10、变量i要增加到n，测试到i=n成立才会终止。故它的频度是n+1。但是它的循环体却只能执行n次。语句(2)作为语句(1)循环体内的语句应该执行n次，但语句(2)本身要执行n+1次，所以语句(2)的频度是n(n+1)。同理可得语句(3)，(4)和(5)的频度分别是n2，n2(n+1)和n3。算法MatrixMultiply的时间耗费T(n)是矩阵阶数n的函数。（2）问题规模和算法的时间复杂度算法求解问题的输入量称为问题的规模(Size),一般用一个整数表示。矩阵乘积问题的规模是矩阵的阶数。一个图论问题的规模则是图中的顶点数或边数。一个算法的时间复杂度(Time Complexity, 也称时间复杂

11、性)T(n)是该算法的时间耗费，是该算法所求解问题规模n的函数。当问题的规模n趋向无穷大时，时间复杂度T(n)的数量级(阶)称为算法的渐进时间复杂度。算法MatrixMultiply的时间复杂度T(n)如(1.1)式所示，当n趋向无穷大时，显然有T(n)O(n3);这表明，当n充分大时，T(n)和n3之比是一个不等于零的常数。即T(n)和n3是同阶的，或者说T(n)和n3的数量级相同。记作T(n)=O(n3)是算法MatrixMultiply的渐近时间复杂度。（3）渐进时间复杂度评价算法时间性能主要用算法时间复杂度的数量级(即算法的渐近时间复杂度)评价一个算法的时间性能。算法MatrixMul

12、tiply的时间复杂度一般为T(n)=O(n3)，f(n)=n3是该算法中语句(5)的频度。下面再举例说明如何求算法的时间复杂度。交换i和j的内容。Temp=i;i=j;j=temp;以上三条单个语句的频度均为1，该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作T(n)=O(1)。注意：如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。变量计数之一：(1) x=0;y=0;(2) for(k-1;k=n;k+)(3) x+;(4) for(i=1;i=n;i+)(5) for(

13、j=1;j=n;j+)(6) y+;一般情况下，对步进循环语句只需考虑循环体中语句的执行次数，忽略该语句中步长加1、终值判别、控制转移等成分。因此，以上程序段中频度最大的语句是(6)，其频度为f(n)=n2，所以该程序段的时间复杂度为T(n)=O(n2)。当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。变量计数之二：(1) x=1;(2) for(i=1;i=n;i+)(3) for(j=1;j=i;j+)(4) for(k=1;k=0&(Ai!=k)(3) i-;(4)return i;此算法中的语句(3)的频度不仅与问题规模n有关，还与输入

14、实例中A的各元素取值及K的取值有关:若A中没有与K相等的元素，则语句(3)的频度f(n)=n；若A的最后一个元素等于K,则语句(3)的频度f(n)是常数0。3空间复杂度编辑与时间复杂度类似，空间复杂度是指算法在计算机内执行时所需存储空间的度量。记作:S(n)=O(f(n)算法执行期间所需要的存储空间包括3个部分：算法程序所占的空间；输入的初始数据所占的存储空间；算法执行过程中所需要的额外空间。在许多实际问题中，为了减少算法所占的存储空间，通常采用压缩存储技术。复杂度分析编辑通常一个算法的复杂度是由其输入量决定的，随着输入的增加，复杂度不同算法的复杂度增长速度如右图所示：为了降低算法复杂度，应当

15、同时考虑到输入量，设计较好的算法。3、算法复杂度分析一 、时间复杂度 算法复杂度分为时间复杂度和空间复杂度。其作用：时间复杂度是度量算法执行的时间长短；而空间复杂度是度量算法所需存储空间的大小。任何算法运行所需要的时间几乎总是取决于他所处理的数据量，在这里我们主要说时间复杂度。对于一个给定计算机的算法程序，我们能画出运行时间的函数图。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。1. 一般情况下，算法的基本操作重复执行的次数是模块n的某一个函数f（n），因此，算法的时间复杂度记做：T（n）=O（f（n）分析：随着模块n的增大，算法执行的时间的增长率和f（n）的增长率成正比，所以

16、f（n）越小，算法的时间复杂度越低，算法的效率越高。2. 在计算时间复杂度的时候，先找出算法的基本操作，然后根据相应的各语句确定它的执行次数，再找出T（n）的同数量级（它的同数量级有以下：1Log2n n nLog2n n的平方n的三次方2的n次方n！），找出后，f（n）=该数量级，若T(n)/f(n)求极限可得到一常数c，则时间复杂度T（n）=O（f（n）,例：javaview plaincopy1. for（i=1;i=n;+i）2. 3. for(j=1;j=n;+j)4. 5. cij=0;/该步骤属于基本操作执行次数：n的平方次6. for(k=1;k=n;+k)7. cij+=ai

17、k*bkj;/该步骤属于基本操作执行次数：n的三次方次8. 9. 则有 T（n）= n的平方+n的三次方，根据上面括号里的同数量级，我们可以确定 n的三次方 为T（n）的同数量级,则有f（n）= n的三次方，然后根据T（n）/f（n）求极限可得到常数c。则该算法的 时间复杂度：T（n）=O（n3） 注：n3即是n的3次方。3.在pascal中比较容易理解，容易计算的方法是：看看有几重for循环，只有一重则时间复杂度为O（n）,二重则为O（n2），依此类推，如果有二分则为O(logn)，二分例如快速幂、二分查找，如果一个for循环套一个二分，那么时间复杂度则为O(nlogn)。按数量级递增排列，

18、常见的时间复杂度有：常数阶O(1),对数阶O(log2n),线性阶O(n),线性对数阶O(nlog2n),平方阶O(n2)，立方阶O(n3),.，k次方阶O(nk), 指数阶O(2n) 。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。根据定义，可以归纳出基本的计算步骤 1. 计算出基本操作的执行次数T(n) 基本操作即算法中的每条语句（以;号作为分割），语句的执行次数也叫做语句的频度。在做算法分析时，一般默认为考虑最坏的情况。 2. 计算出T(n)的数量级 求T(n)的数量级，只要将T(n)进行如下一些操作： 忽略常量、低次幂和最高次幂的系数，令f(n)=T(n)的数量

19、级。 3. 用大O来表示时间复杂度 当n趋近于无穷大时，如果lim(T(n)/f(n)的值为不等于0的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)。 一个示例：javaview plaincopy1. intnum1,num2;2. for(inti=0;in;i+)3. num1+=1;4. for(intj=1;j=n;j*=2)5. num2+=num1;6. 7. 分析：1. 语句int num1, num2;的频度为1； 语句i=0;的频度为1； 语句in; i+; num1+=1; j=1; 的频度为n； 语句j=n; j*=2; num2+=num1;的

20、频度为n*log2n； T(n) = 2 + 4n + 3n*log2n2. 忽略掉T(n)中的常量、低次幂和最高次幂的系数，f(n) = n*log2n3. lim(T(n)/f(n) = (2+4n+3n*log2n) / (n*log2n) = 2*(1/n)*(1/log2n) + 4*(1/log2n) + 3当n趋向于无穷大，1/n趋向于0，1/log2n趋向于0所以极限等于3。T(n) = O(n*log2n)简化的计算步骤 再来分析一下，可以看出，决定算法复杂度的是执行次数最多的语句，这里是num2 += num1，一般也是最内循环的语句。并且，通常将求解极限是否为常量也省略掉

21、？于是，以上步骤可以简化为： 1. 找到执行次数最多的语句 2. 计算语句执行次数的数量级 3. 用大O来表示结果 继续以上述算法为例，进行分析：1. 执行次数最多的语句为num2 += num12. T(n) = n*log2n f(n) = n*log2n3. / lim(T(n)/f(n) = 1 T(n) = O(n*log2n) 二、插入排序算法的时间复杂度 现在研究一下插入排序算法的执行时间，按照习惯，输入长度LEN以下用n表示。设循环中各条语句的执行时间分别是c1、c2、c3、c4、c5这样五个常数：javaview plaincopy1. voidinsertion_sort(

22、void)执行时间2. 3. inti,j,key;4. for(j=1;j=0&aikey)8. ai+1=ai;c39. i-;c410. 11. ai+1=key;c512. 13. 显然外层for循环的执行次数是n-1次，假设内层的while循环执行m次，则总的执行时间粗略估计是(n-1)*(c1+c2+c5+m*(c3+c4)。当然，for和while后面()括号中的赋值和条件判断的执行也需要时间，而我没有设一个常数来表示，这不影响我们的粗略估计。这里有一个问题，m不是个常数，也不取决于输入长度n，而是取决于具体的输入数据。在最好情况下，数组a的原始数据已经排好序了，while循环一

23、次也不执行，总的执行时间是(c1+c2+c5)*n-(c1+c2+c5)，可以表示成an+b的形式，是n的线性函数（Linear Function）。那么在最坏情况（Worst Case）下又如何呢？所谓最坏情况是指数组a的原始数据正好是从大到小排好序的，请读者想一想为什么这是最坏情况，然后把上式中的m替换掉算一下执行时间是多少。数组a的原始数据属于最好和最坏情况的都比较少见，如果原始数据是随机的，可称为平均情况（Average Case）。如果原始数据是随机的，那么每次循环将已排序的子序列a1.j-1与新插入的元素key相比较，子序列中平均都有一半的元素比key大而另一半比key小，请读者把

24、上式中的m替换掉算一下执行时间是多少。最后的结论应该是：在最坏情况和平均情况下，总的执行时间都可以表示成an2+bn+c的形式，是n的二次函数（Quadratic Function）。在分析算法的时间复杂度时，我们更关心最坏情况而不是最好情况，理由如下：1. 最坏情况给出了算法执行时间的上界，我们可以确信，无论给什么输入，算法的执行时间都不会超过这个上界，这样为比较和分析提供了便利。2. 对于某些算法，最坏情况是最常发生的情况，例如在数据库中查找某个信息的算法，最坏情况就是数据库中根本不存在该信息，都找遍了也没有，而某些应用场合经常要查找一个信息在数据库中存在不存在。3. 虽然最坏情况是一种悲

25、观估计，但是对于很多问题，平均情况和最坏情况的时间复杂度差不多，比如插入排序这个例子，平均情况和最坏情况的时间复杂度都是输入长度n的二次函数。 比较两个多项式a1n+b1和a2n2+b2n+c2的值（n取正整数）可以得出结论：n的最高次指数是最主要的决定因素，常数项、低次幂项和系数都是次要的。比如100n+1和n2+1，虽然后者的系数小，当n较小时前者的值较大，但是当n100时，后者的值就远远大于前者了。如果同一个问题可以用两种算法解决，其中一种算法的时间复杂度为线性函数，另一种算法的时间复杂度为二次函数，当问题的输入长度n足够大时，前者明显优于后者。因此我们可以用一种更粗略的方式表示算法的时

26、间复杂度，把系数和低次幂项都省去，线性函数记作(n)，二次函数记作(n2)。(g(n)表示和g(n)同一量级的一类函数，例如所有的二次函数f(n)都和g(n)=n2属于同一量级，都可以用(n2)来表示，甚至有些不是二次函数的也和n2属于同一量级，例如2n2+3lgn。“同一量级”这个概念可以用下图来说明（该图出自算法导论）：图11.2.-notation 如果可以找到两个正的常数c1和c2，使得n足够大的时候（也就是nn0的时候）f(n)总是夹在c1g(n)和c2g(n)之间，就说f(n)和g(n)是同一量级的，f(n)就可以用(g(n)来表示。以二次函数为例，比如1/2n2-3n，要证明它是

27、属于(n2)这个集合的，我们必须确定c1、c2和n0，这些常数不随n改变，并且当nn0以后，c1n21/2n2-3nc2n2总是成立的。为此我们从不等式的每一边都除以n2，得到c11/2-3/nc2。见下图：图11.3.1/2-3/n 这样就很容易看出来，无论n取多少，该函数一定小于1/2，因此c2=1/2，当n=6时函数值为0，n6时该函数都大于0，可以取n0=7，c1=1/14，这样当nn0时都有1/2-3/nc1。通过这个证明过程可以得出结论，当n足够大时任何an2+bn+c都夹在c1n2和c2n2之间，相对于n2项来说bn+c的影响可以忽略，a可以通过选取合适的c1、c2来补偿。 几种

28、常见的时间复杂度函数按数量级从小到大的顺序依次是：(lgn)，(sqrt(n)，(n)，(nlgn)，(n2)，(n3)，(2n)，(n!)。其中，lgn通常表示以10为底n的对数，但是对于-notation来说，(lgn)和(log2n)并无区别（想一想这是为什么），在算法分析中lgn通常表示以2为底n的对数。可是什么算法的时间复杂度里会出现lgn呢？回顾插入排序的时间复杂度分析，无非是循环体的执行时间乘以循环次数，只有加和乘运算，怎么会出来lg呢？下一节归并排序的时间复杂度里面就有lg，请读者留心lg运算是从哪出来的。 除了-notation之外，表示算法的时间复杂度常用的还有一种Big-

29、O notation。我们知道插入排序在最坏情况和平均情况下时间复杂度是(n2)，在最好情况下是(n)，数量级比(n2)要小，那么总结起来在各种情况下插入排序的时间复杂度是O(n2)。的含义和“等于”类似，而大O的含义和“小于等于”类似。受内存管理机影响，指令的执行时间不一定是常数，但执行时间的上界（Upper Bound）肯定是常数，我们这里假设语句的执行时间是常数只是一个粗略估计。 三、常用的算法的时间复杂度和空间复杂度排序法最差时间分析平均时间复杂度稳定度空间复杂度冒泡排序O(n2)O(n2)稳定O(1)快速排序O(n2)O(n*log2n)不稳定O(log2n)O(n)选择排序O(n2

30、)O(n2)稳定O(1)二叉树排序O(n2)O(n*log2n)不一顶O(n)插入排序O(n2)O(n2)稳定O(1)堆排序O(n*log2n)O(n*log2n)不稳定O(1)希尔排序OO不稳定O(1)4、算法时间复杂度分析基础摘要 本文论述了在算法分析领域一个重要问题时间复杂度分析的基础内容。本文将首先明确时间复杂度的意义，而后以形式化方式论述其在数学上的定义及相关推导。从而帮助大家从本质上认清这个概念。前言 通常，对于一个给定的算法，我们要做两项分析。第一是从数学上证明算法的正确性，这一步主要用到形式化证明的方法及相关推理模式，如循环不变式、数学归纳法等。而在证明算法是正确的基础上，第二

31、部就是分析算法的时间复杂度。算法的时间复杂度反映了程序执行时间随输入规模增长而增长的量级，在很大程度上能很好反映出算法的优劣与否。因此，作为程序员，掌握基本的算法时间复杂度分析方法是很有必要的。 但是很多朋友并不能清晰的理解这一概念，究其原因，主要是因为没有从数学层面上理解其本质，而是习惯于从直观理解。下面，我们就一步步走近算法时间复杂度的数学本质。算法时间复杂度的数学意义 从数学上定义，给定算法A，如果存在函数F(n)，当n=k时，F(k)表示算法A在输入规模为k的情况下的运行时间，则称F(n)为算法A的时间复杂度。 这里我们首先要明确输入规模的概念。关于输入规模，不是很好下定义，非严格的讲

32、，输入规模是指算法A所接受输入的自然独立体的大小。例如，对于排序算法来说，输入规模一般就是待排序元素的个数，而对于求两个同型方阵乘积的算法，输入规模可以看作是单个方阵的维数。为了简单起见，在下面的讨论中，我们总是假设算法的输入规模是用大于零的整数表示的，即n=1,2,3,k, 我们还知道，对于同一个算法，每次执行的时间不仅取决于输入规模，还取决于输入的特性和具体的硬件环境在某次执行时的状态。所以想要得到一个统一精确的F(n)是不可能的。为了解决这个问题，我们做一下两个说明： 1.忽略硬件及环境因素，假设每次执行时硬件条件和环境条件是完全一致的。 2.对于输入特性的差异，我们将从数学上进行精确分

33、析并带入函数解析式。算法时间复杂度分析示例 为了便于朋友们理解，我将不会采用教科书上惯用的快速排序、合并排序等经典示例进行分析，而是使用一个十分简单的算法作为示例。我们先来定义问题。 问题定义： 输入此问题输入为一个有序序列，其元素个数为n，n为大于零的整数。序列中的元素为从1到n这n个整数，但其顺序为完全随机。 输出元素n所在的位置。（第一个元素位置为1） 这个问题非常简单，下面直接给出其解决算法之一（伪代码）：LocationN(A) for(int i=1;i=n;i+)-t1 if(Ai = n) -t2 return i;-t3 我们来看看这个算法。其中t1、t2和t3分别表示此行代码执行一次需要的时间。 首先，输入规模n是影响算法执行时间的因素之一。在n固定的情况下，不同的输入序列也会影响其执行时间。最好情况下，n就排在序列的第一个位置，那么此时的运行时间为“t1