关于欧几里得算法的时间复杂度 -- 简明现代魔法6603人阅读
数据结构与算法（1）
& & & & 相信学习编程的同学，或多或少都接触到算法的时间复杂度和空间复杂度了，那我来讲讲怎么计算。
& & & &常用的算法的时间复杂度和空间复杂度 一，求解算法的时间复杂度，其具体步骤是：
　　⑴&找出算法中的基本语句；
　　算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。
　　⑵&计算基本语句的执行次数的数量级；
　　只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析，并且使注意力集中在最重要的一点上：增长率。
　　⑶&用大O记号表示算法的时间性能。
　　将基本语句执行次数的数量级放入大O记号中。
　　如果算法中包含嵌套的循环，则基本语句通常是最内层的循环体，如果算法中包含并列的循环，则将并列循环的时间复杂度相加。例如：
　　for&(i=1;&i&=n;&i++)
　　x++;
　　for&(i=1;&i&=n;&i++)
　　for&(j=1;&j&=n;&j++)
　　x++;
　　第一个for循环的时间复杂度为O(n)，第二个for循环的时间复杂度为O(n2)，则整个算法的时间复杂度为O(n+n2)=O(n2)。
　　常见的算法时间复杂度由小到大依次为：
　　O(1)＜O(log2n)＜O(n)＜O(nlog2n)＜O(n2)＜O(n3)＜…＜O(2n)＜O(n!)
Ο(1)表示基本语句的执行次数是一个常数，一般来说，只要算法中不存在循环语句，其时间复杂度就是O(1)。O(log2n)、O(n)、O(nlog2n)、O(n2)和O(n3)称为多项式时间，而O(2n)和O(n!)称为指数时间。计算机科学家普遍认为前者是有效算法，把这类问题称为P（Polynomial,多项式）类问题，而把后者称为NP（Non-Deterministic
Polynomial,非确定多项式）问题。
在计算算法时间复杂度时有以下几个简单的程序分析法则:&
& &(1).对于一些简单的输入输出语句或赋值语句,近似认为需要O(1)时间&
& &(2).对于顺序结构,需要依次执行一系列语句所用的时间可采用大O下&求和法则& 求和法则:是指若算法的2个部分时间复杂度分别为 T1(n)=O(f(n))和 T2(n)=O(g(n)),则 T1(n)+T2(n)=O(max(f(n),g(n)))。特别地,若T1(m)=O(f(m)), T2(n)=O(g(n)),则 T1(m)+T2(n)=O(f(m)+g(n))&
& &(3).对于选择结构,如if语句,它的主要时间耗费是在执行then字句或else字句所用的时间,需注意的是检验条件也需要O(1)时间&
& &(4).对于循环结构,循环语句的运行时间主要体现在多次迭代中执行循环体以及检验循环条件的时间耗费,一般可用大O下&乘法法则&&
乘法法则: 是指若算法的2个部分时间复杂度分别为 T1(n)=O(f(n))和 T2(n)=O(g(n)),则 T1*T2=O(f(n)*g(n))&
& &(5).对于复杂的算法,可以将它分成几个容易估算的部分,然后利用求和法则和乘法法则技术整个算法的时间复杂度&
& &另外还有以下2个运算法则:(1) 若g(n)=O(f(n)),则O(f(n))+O(g(n))=O(f(n))；(2)O(Cf(n)) = O(f(n)),其中C是一个正常数。
几个常见的时间复杂度进行示例说明：
(1)、O(1)&
&Temp=i; i=j; j= & & & & & & & & & &&
& &以上三条单个语句的频度均为1，该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作T(n)=O(1)。注意：如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。&
（2)、O(n2)
交换i和j的内容
1.sum=0；（一次） &&
2.for(i=1;i&=n;i++) （n+1次） &&
3.for(j=1;j&=n;j++)（n（n+1）次） &&
4.sum++；（n（n+1）+1次）&
因为(2n2+n+1)=n2（即：去低阶项，去掉常数项，去掉高阶项的常参得到），所以T(n)= =O(n2)；
一般情况下，对步进循环语句只需考虑循环体中语句的执行次数，忽略该语句中步长加1、终值判别、控制转移等成分，当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。
(3)、O(n) &
2.b=1; & & & & & & & ① &&
3.for (i=1;i&=n;i++) ② &&
4.{s=a+b; & & & & & &③ &&
6.b=a; & & & & & & & ④ & &&
}& & & & & & &⑤&
语句1的频度为2,语句2的频度为n,语句3的频度为n-1,语句4的频度为n-1,语句5的频度为n-1, 即T(n)=2+n+3(n-1)=4n-1=O(n).&
(4)、O(log2n)&
1. i=1; & ① &&
2. while (i&=n) &&
3. i=i*2; ②&
语句1的频度是1,设语句2的频度是f(n),则：2^f(n)&=n;f(n)&=log2n，取最大值f(n)=log2n,即T(n)=O(log2n)&
(5)、O(n3) &
1. for(i=0;i&n;i++){ & &&
2. for(j=0;j&i;j++){ &&
3.for(k=0;k&j;k++) &&
4.x=x+2; }}
当i=m,j=k的时候,内层循环的次数为k当i=m时, j可以取 0,1,...,m-1 ,所以这里最内循环共进行了0+1+...+m-1=(m-1)m/2次所以,i从0取到n,则循环共进行了:0+(1-1)*1/2+...+(n-1)n/2=n(n+1)(n-1)/6所以时间复杂度为O(n3).
二，算法的空间复杂度：
类似于时间复杂度的讨论，一个算法的空间复杂度(Space Complexity)S(n)定义为该算法所耗费的存储空间，它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。&空间复杂度(Space
Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。算法的输入输出数据所占用的存储空间是由要解决的问题决定的，是通过参数表由调用函数传递而来的，它不随本算法的不同而改变。存储算法本身所占用的存储空间与算法书写的长短成正比，要压缩这方面的存储空间，就必须编写出较短的算法。算法在运行过程中临时占用的存储空间随算法的不同而异，有的算法只需要占用少量的临时工作单元，而且不随问题规模的大小而改变，我们称这种算法是“就地\&进行的，是节省存储的算法，如这一节介绍过的几个算法都是如此；有的算法需要占用的临时工作单元数与解决问题的规模n有关，它随着n的增大而增大，当n较大时，将占用较多的存储单元。
当一个算法的空间复杂度为一个常量，即不随被处理数据量n的大小而改变时，可表示为O(1)；当一个算法的空间复杂度与以2为底的n的对数成正比时，可表示为0(10g2n)；当一个算法的空间复杂度与n成线性比例关系时，可表示为0(n).若形参为数组，则只需要为它分配一个存储由实参传送来的一个地址指针的空间，即一个机器字长空间；若形参为引用方式，则也只需要为其分配存储一个地址的空间，用它来存储对应实参变量的地址，以便由系统自动引用实参变量。
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：6910次
排名：千里之外算法的时间复杂度和空间复杂度-总结
转自：http://blog.csdn.net/xiaoxiaopengbo/article/details/
2840人阅读
本文章已收录于：
-----数据结构和算法-------（10）
算法（11）
算法和数据结构（11）
算法的时间复杂度和空间复杂度-总结
&&&&&&& 通常，对于一个给定的，我们要做 两项分析。第一是从数学上证明算法的正确性，这一步主要用到形式化证明的方法及相关推理模式，如循环不变式、数学归纳法等。而在证明算法是正确的基础上，第二部就是分析算法的时间复杂度。算法的时间复杂度反映了程序执行时间随输入规模增长而增长的量级，在很大程度上能很好反映出算法的优劣与否。因此，作为程序员，掌握基本的算法时间复杂度分析方法是很有必要的。 &&&&&& 算法执行时间需通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量。而度量一个程序的执行时间通常有两种方法。
一、事后统计的方法
&&&&&&&&这种方法可行，但不是一个好的方法。该方法有两个缺陷：一是要想对设计的算法的运行性能进行评测，必须先依据算法编制相应的程序并实际运行；二是所得时间的统计量依赖于计算机的硬件、软件等环境因素，有时容易掩盖算法本身的优势。
二、事前分析估算的方法
&&&&&&& 因事后统计方法更多的依赖于计算机的硬件、软件等环境因素，有时容易掩盖算法本身的优劣。因此人们常常采用事前分析估算的方法。
在编写程序前，依据统计方法对算法进行估算。一个用高级语言编写的程序在计算机上运行时所消耗的时间取决于下列因素：
&&&&&&(1).&算法采用的策略、方法；(2).&编译产生的代码质量；(3).&问题的输入规模；(4).&&机器执行指令的速度。
&&&&&一个算法是由控制结构（顺序、分支和循环3种）和原操作（指固有数据类型的操作）构成的，则算法时间取决于两者的综合效果。为了便于比较同一个问题的不同算法，通常的做法是，从算法中选取一种对于所研究的问题（或算法类型）来说是基本操作的原操作，以该基本操作的重复执行的次数作为算法的时间量度。
1、时间复杂度& （1）时间频度&一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。 （2）时间复杂度&在刚才提到的时间频度中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。 一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=Ｏ(f(n)),称Ｏ(f(n))&为算法的渐进时间复杂度，简称时间复杂度。
&&&&&&&另外，上面公式中用到的 Landau符号其实是由德国数论学家保罗·巴赫曼（Paul Bachmann）在其1892年的著作《解析数论》首先引入，由另一位德国数论学家艾德蒙·朗道（Edmund Landau）推广。Landau符号的作用在于用简单的函数来描述复杂函数行为，给出一个上或下（确）界。在计算算法复杂度时一般只用到大O符号，Landau符号体系中的小o符号、Θ符号等等比较不常用。这里的O，最初是用大写希腊字母，但现在都用大写英语字母O；小o符号也是用小写英语字母o，Θ符号则维持大写希腊字母Θ。 &&&&&& &T (n) = Ο(f (n))&表示存在一个常数C，使得在当n趋于正无穷时总有&T (n) ≤ C * f(n)。简单来说，就是T(n)在n趋于正无穷时最大也就跟f(n)差不多大。也就是说当n趋于正无穷时T (n)的上界是C * f(n)。其虽然对f(n)没有规定，但是一般都是取尽可能简单的函数。例如，O(2n2+n +1) = O (3n2+n+3) = O (7n2&+ n) =&O (&n2&)&，一般都只用O(n2)表示就可以了。注意到大O符号里隐藏着一个常数C，所以f(n)里一般不加系数。如果把T(n)当做一棵树，那么O(f(n))所表达的就是树干，只关心其中的主干，其他的细枝末节全都抛弃不管。 &&&&&&& 在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为O(1),另外，在时间频度不相同时，时间复杂度有可能相同，如T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同，但时间复杂度相同，都为O(n2)。 按数量级递增排列，常见的时间复杂度有：常数阶O(1),对数阶O(log2n),线性阶O(n),&线性对数阶O(nlog2n),平方阶O(n2)，立方阶O(n3),...， k次方阶O(nk),指数阶O(2n)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。
&&&从图中可见，我们应该尽可能选用多项式阶O(nk)的算法，而不希望用指数阶的算法。
&&&&& 常见的算法时间复杂度由小到大依次为：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!)
&&&&&& 一般情况下，对一个问题（或一类算法）只需选择一种基本操作来讨论算法的时间复杂度即可，有时也需要同时考虑几种基本操作，甚至可以对不同的操作赋予不同的权值，以反映执行不同操作所需的相对时间，这种做法便于综合比较解决同一问题的两种完全不同的算法。
（3）求解算法的时间复杂度的具体步骤是：
　　⑴ 找出算法中的基本语句；
　　算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。
　　⑵ 计算基本语句的执行次数的数量级；
　　只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析，并且使注意力集中在最重要的一点上：增长率。
　　⑶ 用大Ο记号表示算法的时间性能。
　　将基本语句执行次数的数量级放入大Ο记号中。
　　如果算法中包含嵌套的循环，则基本语句通常是最内层的循环体，如果算法中包含并列的循环，则将并列循环的时间复杂度相加。例如：
　　第一个for循环的时间复杂度为Ο(n)，第二个for循环的时间复杂度为Ο(n2)，则整个算法的时间复杂度为Ο(n+n2)=Ο(n2)。
　　Ο(1)表示基本语句的执行次数是一个常数，一般来说，只要算法中不存在循环语句，其时间复杂度就是Ο(1)。其中Ο(log2n)、Ο(n)、 Ο(nlog2n)、Ο(n2)和Ο(n3)称为多项式时间，而Ο(2n)和Ο(n!)称为指数时间。计算机科学家普遍认为前者（即多项式时间复杂度的算法）是有效算法，把这类问题称为P（Polynomial,多项式）类问题，而把后者（即指数时间复杂度的算法）称为NP（Non-Deterministic Polynomial, 非确定多项式）问题。
&&&&&&& 一般来说多项式级的复杂度是可以接受的，很多问题都有多项式级的解——也就是说，这样的问题，对于一个规模是n的输入，在n^k的时间内得到结果，称为P问题。有些问题要复杂些，没有多项式时间的解，但是可以在多项式时间里验证某个猜测是不是正确。比如问是不是质数？如果要直接入手的话，那么要把小于的平方根的所有素数都拿出来，看看能不能整除。还好欧拉告诉我们，这个数等于641和6700417的乘积，不是素数，很好验证的，顺便麻烦转告费马他的猜想不成立。大数分解、Hamilton回路之类的问题，都是可以多项式时间内验证一个“解”是否正确，这类问题叫做NP问题。
（4）在计算算法时间复杂度时有以下几个简单的程序分析法则:
(1).对于一些简单的输入输出语句或赋值语句,近似认为需要O(1)时间
(2).对于顺序结构,需要依次执行一系列语句所用的时间可采用大O下"求和法则"
求和法则:是指若算法的2个部分时间复杂度分别为 T1(n)=O(f(n))和 T2(n)=O(g(n)),则 T1(n)+T2(n)=O(max(f(n), g(n)))
特别地,若T1(m)=O(f(m)), T2(n)=O(g(n)),则 T1(m)+T2(n)=O(f(m) + g(n))
(3).对于选择结构,如if语句,它的主要时间耗费是在执行then字句或else字句所用的时间,需注意的是检验条件也需要O(1)时间
(4).对于循环结构,循环语句的运行时间主要体现在多次迭代中执行循环体以及检验循环条件的时间耗费,一般可用大O下"乘法法则"
乘法法则: 是指若算法的2个部分时间复杂度分别为 T1(n)=O(f(n))和 T2(n)=O(g(n)),则 T1*T2=O(f(n)*g(n))
(5).对于复杂的算法,可以将它分成几个容易估算的部分,然后利用求和法则和乘法法则技术整个算法的时间复杂度
另外还有以下2个运算法则:(1) 若g(n)=O(f(n)),则O(f(n))+ O(g(n))= O(f(n))；(2) O(Cf(n)) = O(f(n)),其中C是一个正常数
&（5）下面分别对几个常见的时间复杂度进行示例说明：
&&&&&&& Temp=i; i=j; j=&&&&&&&&&&&&&&&&&&&&
以上三条单个语句的频度均为1，该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作T(n)=O(1)。注意：如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。
(2)、O(n2)
2.1. 交换i和j的内容
解：因为Θ(2n2+n+1)=n2（Θ即：去低阶项，去掉常数项，去掉高阶项的常参得到），所以T(n)= =O(n2)；
解： 语句1的频度是n-1 &&&&&&&&& 语句2的频度是(n-1)*(2n+1)=2n2-n-1 &&&&&&&&& f(n)=2n2-n-1+(n-1)=2n2-2；
&&&&&&& 又Θ(2n2-2)=n2 &&&&&&&&& 该程序的时间复杂度T(n)=O(n2).&&
　　一般情况下，对步进循环语句只需考虑循环体中语句的执行次数，忽略该语句中步长加1、终值判别、控制转移等成分，当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。&&&&&
(3)、O(n)&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
解： 语句1的频度：2,&&&&&&&& &&&&&&&&&& 语句2的频度： n,&&&&&&&& &&&&&&&&& 语句3的频度： n-1,&&&&&&&& &&&&&&&&& 语句4的频度：n-1,&&&& &&&&&&&&& 语句5的频度：n-1,&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& &&&&&&&&& T(n)=2+n+3(n-1)=4n-1=O(n). (4)、O(log2n)
解： 语句1的频度是1,&& &&&&&&&&& 设语句2的频度是f(n),&& 则：2^f(n)&=n;f(n)&=log2n&&&& &&&&&&&&& 取最大值f(n)=log2n, &&&&&&&&& T(n)=O(log2n&)
(5)、O(n3)&
解：当i=m, j=k的时候,内层循环的次数为k当i=m时, j 可以取 0,1,...,m-1 , 所以这里最内循环共进行了0+1+...+m-1=(m-1)m/2次所以,i从0取到n, 则循环共进行了: 0+(1-1)*1/2+...+(n-1)n/2=n(n+1)(n-1)/6所以时间复杂度为O(n3).
（5）常用的算法的时间复杂度和空间复杂度
一个经验规则：其中c是一个常量，如果一个算法的复杂度为c 、&log2n&、n 、 n*log2n&,那么这个算法时间效率比较高 ，如果是2n&,3n&,n!，那么稍微大一些的n就会令这个算法不能动了，居于中间的几个则差强人意。
&&&&&&&算法时间复杂度分析是一个很重要的问题，任何一个程序员都应该熟练掌握其概念和基本方法，而且要善于从数学层面上探寻其本质，才能准确理解其内涵。
2、算法的空间复杂度
&&&&&&& 类似于时间复杂度的讨论，一个算法的空间复杂度(Space Complexity)S(n)定义为该算法所耗费的存储空间，它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。 空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。算法的输入输出数据所占用的存储空间是由要解决的问题决定的，是通过参数表由调用函数传递而来的，它不随本算法的不同而改变。存储算法本身所占用的存储空间与算法书写的长短成正比，要压缩这方面的存储空间，就必须编写出较短的算法。算法在运行过程中临时占用的存储空间随算法的不同而异，有的算法只需要占用少量的临时工作单元，而且不随问题规模的大小而改变，我们称这种算法是“就地\"进行的，是节省存储的算法，如这一节介绍过的几个算法都是如此；有的算法需要占用的临时工作单元数与解决问题的规模n有关，它随着n的增大而增大，当n较大时，将占用较多的存储单元，例如将在第九章介绍的快速排序和归并排序算法就属于这种情况。
如当一个算法的空间复杂度为一个常量，即不随被处理数据量n的大小而改变时，可表示为O(1)；当一个算法的空间复杂度与以2为底的n的对数成正比时，可表示为0(10g2n)；当一个算法的空I司复杂度与n成线性比例关系时，可表示为0(n).若形参为数组，则只需要为它分配一个存储由实参传送来的一个地址指针的空间，即一个机器字长空间；若形参为引用方式，则也只需要为其分配存储一个地址的空间，用它来存储对应实参变量的地址，以便由系统自动引用实参变量。
原文链接：
我的同类文章
-----数据结构和算法-------（10）
算法（11）
算法和数据结构（11）您所在位置： &
&nbsp&&nbsp&nbsp&&nbsp
简称算法的时间复杂度.ppt 44页
本文档一共被下载：
次 ,您可全文免费在线阅读后下载本文档。
需要金币：120 &&
简称算法的时间复杂度
你可能关注的文档：
······
··········
第二章算法分析基础算法分析的任务:对设计出的每一个具体的算法,利用数学工具，讨论其复杂度。上节下节2.1算法分析体系及计量对算法的评价有两个大的方面：一是人对算法的维护的方便性。二是算法在实现运行时占有的机器资源的多少即算法的运行的时间和空间效率。上节下节2.1.1算法分析的评价体系人对算法的维护主要有编写、调试、改正和功能扩充等工作,这就需要在算法设计时注重算法的可读性。为了算法的利用率,也要考虑算法的适用范围,注重算法的通用性、可重用性和可扩充性。机器对算法的运行效率主要包括时间效率和空间效率。算法在完成功能的前题下最好是占用空间少而且执行时间短。另外在算法实现时,要考虑算法在运行过程中与使用者进行交互的情况。这就要求,算法的交互部分要具有友好性和健壮性。上节下节总之，对算法的分析和评价，一般应考虑正确性、可维护性、可读性、运算量及占用存储空间等诸多因素。其中评价算法的三条主要标准是：(1)算法实现所耗费的时间；(2)算法实现所所耗费的存储空间，其中主要考虑辅助存储空间；(3)算法应易于理解，易于编码，易于调试等等。上节下节1.和算法执行时间相关的因素：1）问题中数据存储的数据结构2）算法采用的数学模型3）算法设计的策略4）问题的规模5）实现算法的程序设计语言6）编译算法产生的机器代码的质量7）计算机执行指令的速度上节下节2.1.2算法的时间复杂性2．算法效率的衡量方法通常有两种衡量算法效率的方法:1）事后统计法（有缺点，较少使用）2）事前分析估算法算法的时间效率是问题规模的函数。假如,随着问题规模n的增长,算法执行时间的增长率和f(n)的增长率相同,则可记作:T(n)=Ο(f(n)),称T(n)为算法的渐近时间复杂度(AsymptoticTimeComplexity),简称时间复杂度。Ο是数量级的符号。上节下节3．时间复杂度估算因为：算法=控制结构+原操作(固有数据类型的操作)所以：算法的执行时间=原操作的执行次数*原操作语句的频度指的是该语句重复执行的次数。一个算法转换为算法后所耗费的时间,除了与所用的计算软、硬件环境有关外，主要取决于算法中指令重复执行的次数，即语句的频度相关。上节下节一个算法中所有语句的频度之和构成了该算法的运行时间。例如：for(j=1;j&=n;++j)for(k=1;k&=n;++k)++x；语句“++x、k&=n、++k”的频度是n2，语句“j=1、k=1”的频度是1，语句“j&=n;++j”的频度是n。算法运行时间为：3*n2+2n+2。上节下节对较复杂的算法计算算法的运行时间,经常从算法中选取一种对于所研究的问题来说是基本(或者说是主要)的原操作,以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则。这个原操作,多数情况下是最深层次循环体内的语句中的原操作。例如：for(i=1;i&=n;++i)for(j=1;j&=n;++j){c[i,j]=0;for(k=0;k&=n;++k)c[i,j]=c[i,j]+a[i,k]*b[k,j];}该算法的基本操作是乘法操作,时间复杂度为n3。上节下节当一个算法的算法运行时间为n2+n+1时，由于n2+n+1与n2的数量级相等(该表达式当n足够大时约等于n2),我们说这个算法的渐进时间复杂度(简称算法的时间复杂度)为：T(n)=O(n2)。数量级相等是这样定义的,设f(n)是一个关于正整数n的函数,若存在一个常数C，使则称f(n)与g(n)是同数量级的函数。上节下节算法(渐进)时间复杂度,一般均表示为以下几种数量级的形式(n为问题的规模,c为一常量)：Ο(1)称为常数级Ο(logn)称为对数级Ο(n)称为线性级Ο(nc)称为多项式级Ο(cn)称为指数级Ο(n!)称为阶乘级上节下节以上时间复杂度级别是由低到高排列的,其随规模n的增长率，由图2-1可见一斑：图2-1T(n)与规模n的函数关系上节下节一般来说如果选用了阶乘级的算法，则当问题规模等于或者大于10时就要认真考虑算法的适用性问题。所以,原则上一个算法的时间复杂度,最好不要采用指数级和阶乘级的算法,而应尽可能选用多项式级或线性级等时间复杂度级别较小的算法。对于较复杂的算法，可将它分隔成容易估算的几个部分，然后再利用&O&的求和原则得到整个算法的时间复杂度。例：若算法的两个部分的时间复杂度分别为T1(n)=O(f(n))和T2(n)=O(g(n))，则总的时间复杂度为：T(n)=T1(n)+T2(n)=O(max(f(n),g(n)))。上节下节4．问题时间复杂度的上界和下界复杂度的上界和下界是用以估计问题所需某资源的复杂程度的界限函数。如果找到解某问题的算法,其资源的复杂度为u(n),则u(n)是问题本身复杂度的一
正在加载中，请稍后...算法的时间复杂度 | 日志 | 果壳网 科技有意思
Edit:用了代码高亮脚本以后超过字数上限高亮后的代码会放在回复里……========首先谢谢小年给开了日志~~然后抄送某个多线程反而比单线程慢的小破孩。。。看了下发现代码缩进神马的都不见了。。。。纳斯达克老师新的脚本里貌似没有更新代码支持部分呢……最后，第一次写科普文，求各种批评指点，尤其是在非技术的方面。。谢谢啦~~=================在信息化的时代里每个人都应该懂一点编程。重复性的机械劳动，都应该交给机器去做，从而把人的精力放在更有挑战性的任务上。写代码第一个要避免的就是syntex error和类似这里（）所写非所想的错误；第二个就是要注意算法的复杂度。一个程序没有bug，但是因为算法不够优化，最后要很长时间才能得出结果，发生这种事呢，大家都不想的。这里就从斐波那契数列入手，来讲讲算法的时间复杂度。0. 准备工作： Landau符号Landau符号其实是由德国数论学家保罗·巴赫曼（Paul Bachmann）在其1892年的著作《解析数论》首先引入，由另一位德国数论学家艾德蒙·朗道（Edmund Landau）推广。Landau符号的作用在于用简单的函数来描述复杂函数行为，给出一个上或下（确）界。在计算算法复杂度时一般只用到大O符号，Landau符号体系中的小o符号、Θ符号等等比较不常用。这里的O，最初是用大写希腊字母，但现在都用大写英语字母O；小o符号也是用小写英语字母o，Θ符号则维持大写希腊字母Θ。f (n) = Ο(g (n)) 表示存在一个常数C，使得在当n趋于正无穷时总有 f (n) ≤ C * g(n)。简单来说，就是f(n)在n趋于正无穷时最大也就跟g(n)差不多大。虽然对g(n)没有规定，但是一般都是取尽可能简单的函数。例如，O(2n^2+n +1) = O (3n^2+n+3) = O (7n^2 + n) = O ( n^2 ) ，一般都只用O(n^2)表示就可以了。注意到大O符号里隐藏着一个常数C，所以g(n)里一般不加系数。如果把f(n)当做一棵树，那么O(g(n))所表达的就是树干，只关心其中的主干，其他的细枝末节全都抛弃不管。在时间复杂度计算中常见的级别有O(1)， O(log n) ， O(n), O(n * log n) , O(n^k)， O(a^n), O(n!)，其大小逐级上升：注意到所有的对数只不过相差一个常数，所以这里都用了常用对数。另外一般程序只处理32位的数据，因此最大整数是2^32-1，大约等于10^9。因此log n可以认为是近似等于10的常数，也就是说O(log n)的近似等于O(1)，O(n * log n)近似等于O(n)，这点也在上表中有所反应。全国有10^9个人，一个人大约有10^14个细胞，一摩尔基本粒子中有10^24个（大致相当于全国人民身上的细胞总数），宇宙中大概有10^80个基本粒子，所以上表中的某些数字，你懂的……1 算法的时间复杂度好了，了解了Landou或者叫大O符号，我们就可以来讨论算法的时间复杂度了。一个算法，对于一个规模是n的输入，需要T(n)的时间进行运算。T(n)的具体值，一方面取决于算法，另一方面和计算用的工具也有关。但我们关心的是，当n扩大100倍以后，T(n)是几乎不变，还是扩大了100倍、10000倍或者怎样。也就是说，我们关心的是规模扩大后，运算时间增长得有多快，是一个相对的结果，而不是绝对结果。建立一个空列表，需要的时间总是固定的，就是O(1)；如果有一句for或者while的语句，把同一行代码运算了n次，那么就是O(n)级的复杂度；如果for下面还有for，各自要算n次，那么就是n^2的复杂度，以此类推。 复杂度举例：*
O(1) 常数级复杂度，也就是说程序运行的时间与需要处理的数据大小无关。通常把比较大小、加减乘除等简单的运算都当做常数级复杂度。 值得注意的是，在处理大数（二进制下数据长度超过32位或者十进制下超过8位）时，将加减乘除等运算当做常数复杂度不再适用。*
O(log n) 将一个10进制整数转化为2进制整数*
O(n)：判断一个元素是否属于一个大小为n的集合/列表；找出n个数中的最大值；*
O(n * log n) 快速排序法*
O(n^2) 最直白的两两比较然后排序方法，需要n*(n-1)/2次比较，所以是O(n^2)级。*
O(2^n) 列出所有长度为n的0,1字符串之类的穷举计算*
O(n!) 列出n个元素的全排列之类的穷举计算一般来说多项式级的复杂度是可以接受的，很多问题都有多项式级的解——也就是说，这样的问题，对于一个规模是n的输入，在n^k的时间内得到结果，称为P问题。有些问题要复杂些，没有多项式时间的解，但是可以在多项式时间里验证某个猜测是不是正确。比如问是不是质数？如果要直接入手的话，那么要把小于的平方根的所有素数都拿出来，看看能不能整除。还好欧拉告诉我们，这个数等于641和6700417的乘积，不是素数，很好验证的，顺便麻烦转告费马他的猜想不成立。大数分解、Hamilton回路之类的问题，都是可以多项式时间内验证一个“解”是否正确，这类问题叫做NP问题。（据信程序猿找妹子也是一个NP问题。。）P问题显然都是NP问题——既然你能在多项式时间里得到答案，那么只要比较一下答案和猜测是不是一样就可以验证一个解。反过来，多数人相信，NP问题不都是P问题。几个月前看到一篇论文说NP不等于P，但没有看到后续报道，也读不懂原文，摊手……如果NP问题都是P问题，那么大数分解不再是难题，从而基于大数分解的RSA加密系统顿时崩溃；同样md5算法也不再有效，甚至现在所有的多项式复杂度的加密算法都没用了——不过这样一来程序猿也可以方便地找到妹子了，说起来并不是一无是处嘛……2 斐波那契数列早在1150年印度科学家Gopala就研究过斐波那契数列，但正如Landau抢走了Landau符号的命名一样，斐波那契也获得了不属于他的数列的冠名权。斐波那契数列是和兔子紧紧联系在一起的。 斐波那契的兔子是这样的一个模型：一开始有一对小兔子。小兔子需要一个月以后才能长成大兔子从而拥有生育能力；所有拥有生育能力的大兔子每个月都会生一对小兔子。所有的兔子都长生不老，问第n个月一共有多少兔子呢？维基百科词条中有这样一张直观的图：让我们列一个表来看看每个月大兔子小兔子各有多少只：从表中我们可以找到这样的规律：F(n)=F(n-1)+F(n-2)这就是斐波那契数列的递推公式，可以用数学归纳法证明。利用一些数学工具我们可以得到斐波那契数列的通项公式：其中小括号里的两个数是方程 x^2-x-1=0的解，跟著名的黄金分割比有密切的关系。用上面的Landau符号，有F(n) = O(^n)，其中是黄金分割比： 所以说，兔子的增长速度还是非常快的……斐波那契数列还可以通过下面的矩阵乘方来实现，这点会在后面的算法中用到。对矩阵不熟悉的读者，暂时可以认为这里2阶矩阵的乘法是两组4元数组之间的运算，结果仍然是一组4元数组；对于相同的矩阵（4元数组），这个运算满足交换律和结合律。
3 三种程序计算斐波那契数列第n项第一种算法，too simple, sometimes naif，直接从递推公式下手：def fibo_1(n): '''
简单递归方法求斐波那契数列第n项。
输入变量n应当为正整数。(对非法输入没有警告） ''' if n & 3:
res=1 #设定初始状态：F(1)=F(2)=1 else:
res=fibo_1(n-1)+fibo_1(n-2) #递归公式 return res这样计算的复杂度是怎样能？让我们看看递归次数：可以看到计算F(n)，需要的递归次数是F(n-2)。指数级的复杂度啊……不行不行，我要提高自身修养，看看第二个算法：def fibo_2(n): '''
通过递归方法求斐波那契数列第n项
变量n应当为正整数。（对非法输入没有警告）
记录最后两项计算结果 ''' a=1 b=1 #设定初始状态，a=F(1),b=F(2) for i in range(2,n):
a,b=a+b,a # 由数学归纳法易得第i步中a=F(i),b=F(i-1) return a #循环结束时i=n，a=F(n)分析：这次好多了，for语句，循环n-2次，O(n)级的复杂度。 最后来个利用矩阵乘方的算法，只需要O(log n)的复杂度，可以跟美国的那个谁谈笑风生了：def fibo_3(n): '''
将求斐波那契数列转化为求2阶矩阵n次幂问题。 ''' def prod(m1,m2):
两个矩阵的乘积
a1,b1,c1,d1=m1
a2,b2,c2,d2=m2
return (a1*a2+b1*c2,a1*b2+c1*d2,a2*c1+c2*d1,b2*c1+d1*d2) def pui(m,n):
求一个矩阵m的n次幂。
如n=2k+1，则m^n=(m^k)^2*m;
如n=2k，则m^n=(m^k)^2。
if n == 1:
res=pui(m,n//2) #上述的k=n//2，//表示带余除法的商，例如 5//2 = 2
res=prod(res,res) #得到上述的(m^k)^2
if n%2==1: # n%2表示n被2除的余数
res=prod(res,m) #如果n是奇数，那么结果还要再乘以m
return res m=(1,1,1,0) #初始化矩阵 (a,b,c,d)=pui(m,n-1) # n次幂的第一项是F(n+1) return a这里用到的乘方算法，对于奇数2k+1，只要先算k次幂，然后自乘，再乘以最初的矩阵；对于偶数2k，只需先算k次幂，然后自乘即可。而计算k次幂时仍然可以采用上面的算法。如果n在2进制表达中一共有m位，并且其中有l个1，那么一共需要进行m+l次乘法，小于2*m=O(log n)。多说无益，让我们来看看三种算法处理相同规模的输入各自要多少时间：def timing(f,n): '''计算f(n)需要多少时间''' import time #载入时间模块 t1=time.time() #读取当前时刻（计算开始时刻） res=f(n) #计算f(n) t2=time.time() #再次读取当前时刻（计算结束时刻） return t2-t1 #两次时刻差值既是计算f(n)所需要的时间，单位为秒第一种天然呆的算法果然弱爆了，算F(30)就要0.6秒；第二种算法算十万要3秒多；第三种算法算一百万也不过3秒不到。上面的算法有一个问题，就是明明第二种算法是线性的，第三种算法是对数级的，但是当我尝试多加一个0时，所需要的时间完全不能忍受，不得不强制停止，大大超过按照前几次测试推算的结果。为什么呢？答案就在于，斐波那契的兔子繁殖特别快，中间过程的数值很快超过了2^32，python不得不启用了大数运算。而数字越大，进行乘法、加法运算所需要的时间也越长，不能再当做常数时间。那么让我们来看看下面这个简化，只求计算结果的末7位，也就是说利用求余数的方法把所有的数字都限制在10^8以内：def fibo_1_bis(n): '''
简单递归方法求斐波那契数列第n项。
输入变量n应当为正整数。(对非法输入没有警告） ''' if n & 3:
res=1 #设定初始状态：F(1)=F(2)=1 else:
res=(fibo_1(n-1)+fibo_1(n-2))% #递归公式 return resdef fibo_2_bis(n): '''
通过递归方法求斐波那契数列第n项
变量n应当为正整数。（对非法输入没有警告）
记录最后两项计算结果 ''' a=1 b=1 #设定初始状态，a=F(1),b=F(2) for i in range(2,n):
a,b=(a+b)%,a # 由数学归纳法易得第i步中a=F(i),b=F(i-1) return a #循环结束时i=n，a=F(n)def fibo_3_bis(n): '''
将求斐波那契数列转化为求2阶矩阵n次幂问题。 ''' def prod(m1,m2):
两个矩阵的乘积
a1,b1,c1,d1=m1
a2,b2,c2,d2=m2
return ((a1*a2+b1*c2)%,(a1*b2+c1*d2)%,(a2*c1+c2*d1)%,(b2*c1+d1*d2)%) def pui(m,n):
求一个矩阵m的n次幂。
如n=2k+1，则m^n=(m^k)^2*m;
如n=2k，则m^n=(m^k)^2。
if n == 1:
res=pui(m,n//2) #上述的k=n//2，//表示带余除法的商，例如 5//2 = 2
res=prod(res,res) #得到上述的(m^k)^2
if n%2==1: # n%2表示n被2除的余数
res=prod(res,m) #如果n是奇数，那么结果还要再乘以m
return res m=(1,1,1,0) #初始化矩阵 (a,b,c,d)=pui(m,n-1) # n次幂的第一项是F(n+1) return a再来看看需要多少时间： 可以看到第一种算法需要的时间基本满足斐波那契的递推公式，和前面的预测相符；第二种算法需要的时间也和预测的线性增长相符；第三种算法，不管我输入多少个0，都是瞬间给出答案，O(log n)级的算法真心屌爆了有没有！！！附python文件fibo.py下载地址：
本文由授权（）发表，文章著作权为原作者所有。
脚本已经修复了，去下载吧！
f(n)=（1/sqrt(5)）*(power(a,n)-power(b,n));a，b分别为(sqrt(5)+1)/2，(sqrt(5)-1)/2;power好像是常数复杂度？
那个谁是华莱士吧…另外python没缩进好难看…
引用maxwell'sdem...的回应：f(n)=（1/sqrt(5)）*(power(a,n)-power(b,n));a，b分别为(sqrt(5)+1)/2，(sqrt(5)-1)/2;power好像是常数复杂度？1 power最好我也只知道有log级的，见矩阵部分；2 a,b都是无理数，最后结果是整数，需要精确处理，占用资源太多了。
引用maxwell'sdem...的回应：f(n)=（1/sqrt(5)）*(power(a,n)-power(b,n));a，b分别为(sqrt(5)+1)/2，(sqrt(5)-1)/2;power好像是常数复杂度？或者可以用形式计算，绕开根号5，但仍然很复杂。
引用Ekoms的回应：1 power最好我也只知道有log级的，见矩阵部分；2 a,b都是无理数，最后结果是整数，需要精确处理，占用资源太多了。pow()好像有牛顿迭代的版本？深度好像是常数
哦？ 求指教！！！！引用maxwell'sdem...的回应：pow()好像有牛顿迭代的版本？深度好像是常数
def fibo_1_bis(n):&&&&'''&&&&&&&&简单递归方法求斐波那契数列第n项。&&&&&&&&输入变量n应当为正整数。(对非法输入没有警告）&&&&'''&&&&if n & 3:&&&&&&&&res=1 #设定初始状态：F(1)=F(2)=1&&&&else:&&&&&&&&res=(fibo_1(n-1)+fibo_1(n-2))% #递归公式&&&&return res
def fibo_2_bis(n):&&&&'''&&&&&&&&通过递归方法求斐波那契数列第n项&&&&&&&&变量n应当为正整数。（对非法输入没有警告）&&&&&&&&记录最后两项计算结果&&&&'''&&&&a=1&&&&b=1 #设定初始状态，a=F(1),b=F(2)&&&&for i in range(2,n):&&&&&&&&a,b=(a+b)%,a # 由数学归纳法易得第i步中a=F(i),b=F(i-1)&&&&return a #循环结束时i=n，a=F(n)
def prod(m1,m2):&&&&'''&&&&&&&&两个矩阵的乘积&&&&'''&&&&a1,b1,c1,d1=m1&&&&a2,b2,c2,d2=m2&&&&return ((a1*a2+b1*c2)%,(a1*b2+c1*d2)%,(a2*c1+c2*d1)%,(b2*c1+d1*d2)%)
def pui(m,n):&&&&'''&&&&&&&&求一个矩阵m的n次幂。&&&&&&&&如n=2k+1，则m^n=(m^k)^2*m;&&&&&&&&如n=2k，则m^n=(m^k)^2。&&&&'''&&&&if n == 1:&&&&&&&&return m&&&&else:&&&&&&&&res=pui(m,n//2) #上述的k=n//2，//表示带余除法的商，例如 5//2 = 2&&&&&&&&res=prod(res,res) #得到上述的(m^k)^2&&&&&&&&if n%2==1: # n%2表示n被2除的余数&&&&&&&&&&&&res=prod(res,m) #如果n是奇数，那么结果还要再乘以m&&&&&&&&return res
def fibo_3_bis(n):&&&&'''&&&&&&&&将求斐波那契数列转化为求2阶矩阵n次幂问题。&&&&'''&&&&m=(1,1,1,0) #初始化矩阵&&&&(a,b,c,d)=pui(m,n-1) # n次幂的第一项是F(n+1)&&&&return a
def timing(f,n):&&&&'''计算f(n)需要多少时间'''&&&&import time #载入时间模块&&&&t1=time.time() #读取当前时刻（计算开始时刻）&&&&res=f(n) #计算f(n)&&&&t2=time.time() #再次读取当前时刻（计算结束时刻）&&&&return t2-t1 #两次时刻差值既是计算f(n)所需要的时间，单位为秒
引用Ekoms的回应：哦？ 求指教！！！！只是听说……
没人吐槽那个漫画么……
搞算法的人真牛逼，膜拜一下~
这不就是算法设计课本的第一章吗？……
引用Clones的回应：这不就是算法设计课本的第一章吗？……啊？
最近怎么没见你来死理性派小组晃晃了？
引用吴师傅的回应：最近怎么没见你来死理性派小组晃晃了？偶尔还是看看的，但是很多帖子/回复实在是。。唉……
(C)2017果壳网&&&&京ICP证100430号&&&&京网文[-239号&&&&新出发京零字东150005号&&&&
违法和不良信息举报邮箱：&&&&举报电话：