算法学习 机器学习

编程之算法时间复杂度

2017-05-26  本文已影响381人  KODIE
Snip20170526_404.png

算法复杂度

什么是时间复杂度

算法执行时间需通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量

怎么度量程序执行时间

决定时间消耗的因素

具体度量方式

时间复杂度与时间频度

时间频度

时间复杂度

Landau符号:上面的O是符号中的一个

常见的时间复杂度

在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为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的不断增大，上述时间复杂度不断增大，算法的执行效率越低。

常见的算法时间复杂度由小到大依次为：
Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!)

求解时间复杂度的步骤

计算时间复杂度示例：

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

PS:
Ο(1)表示基本语句的执行次数是一个常数，一般来说，只要算法中不存在循环语句，其时间复杂度就是Ο(1)。其中Ο(log2n)、Ο(n)、 Ο(nlog2n)、Ο(n2)和Ο(n3)称为多项式时间，而Ο(2n)和Ο(n!)称为指数时间。计算机科学家普遍认为前者（即多项式时间复杂度的算法）是有效算法，把这类问题称为P（Polynomial,多项式）类问题，而把后者（即指数时间复杂度的算法）称为NP（Non-Deterministic Polynomial, 非确定多项式）问题。
一般来说多项式级的复杂度是可以接受的，很多问题都有多项式级的解——也就是说，这样的问题，对于一个规模是n的输入，在n^k的时间内得到结果，称为P问题。有些问题要复杂些，没有多项式时间的解，但是可以在多项式时间里验证某个猜测是不是正确。比如问4294967297是不是质数？如果要直接入手的话，那么要把小于4294967297的平方根的所有素数都拿出来，看看能不能整除。还好欧拉告诉我们，这个数等于641和6700417的乘积，不是素数，很好验证的，顺便麻烦转告费马他的猜想不成立。大数分解、Hamilton回路之类的问题，都是可以多项式时间内验证一个“解”是否正确，这类问题叫做NP问题。

计算时间复杂度的分析法则

求和法则:
是指若算法的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))

乘法法则: 
是指若算法的2个部分时间复杂度分别为 T1(n)=O(f(n))和 T2(n)=O(g(n)),
则 T1*T2=O(f(n)*g(n))

另外还有以下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，该程序段的执行时间是一个与问题规模n无关的常数。
算法的时间复杂度为常数阶，记作T(n)=O(1)。
注意：如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。
此类算法的时间复杂度是O(1)。

sum=0；                 （一次）  
for(int i = 1; i <= n; i++)     （n+1次）  
      for(int j = 1; j <= n; j++) （n2次）  
           sum++；            （n2次）

解：

因为Θ(2n2+n+1)=n2（Θ即：去低阶项，去掉常数项，去掉高阶项的常参得到）
所以T(n)= =O(n2)；

for (int i = 1; i < n; i++)  
 {   
       y = y + 1;         ①     
       for (int j = 0; j <= (2 * n); j++)      
            x++;         ②        
 }

解：

语句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).

PS: 一般情况下，对步进循环语句只需考虑循环体中语句的执行次数，忽略该语句中步长加1、终值判别、控制转移等成分，当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。

int s;
int a = 0;  
int b = 1;                      ①  
  for (int i = 1; i <= n; i++) ②  
  {    
     s = a + b;　　　　③  
     b = a;　　　　　④    
     a = s;　　　　　⑤  
  }

解：

语句1的频度：2,        
语句2的频度： n,        
语句3的频度： n-1,        
语句4的频度：n-1,    
语句5的频度：n-1,                                  
T(n)=2+n+3(n-1)=4n-1=O(n).

int i = 1;     ①  
while (i <= n)  
  i = i * 2; ②

解：

语句1的频度是1,  
设语句2的频度是f(n),   则：2^f(n)<=n;f(n)<=log2n    
取最大值f(n)=log2n,
T(n)=O(log2n )

for(int i = 0; i < n; i++)  
   {    
      for(int j = 0; j < i; j++)    
      {  
         for(int k = 0; k < j; k++)  
            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).

常用算法的时间复杂度

Snip20170526_410.png

空间复杂度

常用时间复杂度的记法

参考

以上！

小七
上一篇 下一篇

猜你喜欢

热点阅读