重新认识算法的时间复杂度

  发布日期:   2018-06-14
  最新修改:   2020-10-22
  阅读次数:   83 次
  • 更多分享:www.catbro.cn
  • 最近在重新温习算法,突然对于时间复杂这概念,觉得还是有必要从新捋一捋

1.时间复杂度

  • 提到时间复杂度,第一时间想到的是算法,简单说,算法就是你解决问题的方法,而你用这个方法解决这个问题所执行的语句次数,称为语句频度或者时间频度,记为T(n)。

  • 那么问题来了,我们为什么要引入这些个概念呢。因为我们想要的是执行一个算法耗费的时间,这个时间理论上可以得到,但是,要得到这个时间就必须要上机测试,但是有这个必要吗?我们需要知道的是哪一个算法需要的时间多,哪一个算法需要的时间少,这样就可以了。而且,算法的耗时和语句的执行次数是成正比的,即语句执行越多,耗时越多。这也就是我们引入概念的原因。

  • 在上面提到的时间频度T(n)中,n是指算法的规模,n不断的变化,T(n)就会不断的变化,而这些变化的规律是怎样的呢?于是我们引入了时间复杂度的概念。

  • 什么是时间复杂度,算法中某个函数有n次基本操作重复执行,用T(n)表示,现在有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。通俗一点讲,其实所谓的时间复杂度,就是找了一个同样曲线类型的函数f(n)来表示这个算法的在n不断变大时的趋势 。当输入量n逐渐加大时,时间复杂性的极限情形称为算法的“渐近时间复杂性”。

  • 我们用大O表示法表示时间复杂性,它是一个算法的时间复杂性。大O表示只是说有上界但并不是上确界。
  • “大O记法”:在这种描述中使用的基本参数是 n,即问题实例的规模,把复杂性或运行时间表达为n的函数。这里的“O”表示量级 (order),比如说“二分检索是 O(logn)的”,也就是说它需要“通过logn量级的步骤去检索一个规模为n的数组”记法 O ( f(n) )表示当 n增大时,运行时间至多将以正比于 f(n)的速度增长。
  • 时间复杂度对于算法进行的分析和大致的比较非常有用,但是真正的情况可能会因为一些其他因素造成差异。比如一个低附加代价的O(n2)算法在n较小的情况下可能比一个高附加代价的 O(nlogn)算法运行得更快。但是,n越来越大以后,相比较而言较慢上升函数的算法会运行的更快。
  • 上面我引用了一些专业的定义,可能并不是太好理解,下面会写一些常出现的算法时间复杂度和一些实例来解释一下。

2.简单算法的时间复杂度举例

  • 列举一些简单例子的时间复杂度。

  • O(1)的算法是一些运算次数为常数的算法。例如:

      temp=a;a=b;b=temp;
  • 上面语句共三条操作,单条操作的频度为1,即使他有成千上万条操作,也只是个较大常数,这一类的时间复杂度为O(1)。

  • O(n)的算法是一些线性算法。例如:

     sum=0;                 
     for(i=0;i<n;i++)       
         sum++;
  • 上面代码中第一行频度1,第二行频度为n,第三行频度为n,所以f(n)=n+n+1=2n+1。所以时间复杂度O(n)。这一类算法中操作次数和n正比线性增长。

  • O(logn) 一个算法如果能在每个步骤去掉一半数据元素,如二分检索,通常它就取 O(logn)时间。举个栗子:

    int i=1; 
    while (i<=n) 
       i=i*2; 
  • 上面代码设第三行的频度是f(n), 则:2*f(n)<=n;f(n)<=log₂n,取最大值f(n)= log₂n,所以T(n)=O(log₂n ) 。

  • O(n²)(n的k次方的情况)最常见的就是平时的对数组进行排序的各种简单算法都是O(n²),例如直接插入排序的算法。

  • 而像矩阵相乘算法运算则是O(n³)。

  • 举个简单栗子:

    sum=0;                
    
     for(i=0;i<n;i++)  
    
        for(j=0;j<n;j++) 
    
           sum++;
  • 第一行频度1,第二行n,第三行n²,第四行n²,T(n)=2n²+n+1 =O(n²)

  • O(2的n次方) 比如求具有n个元素集合的所有子集的算法

  • O(n!) 比如求具有N个元素的全排列的算法

  • 时间复杂度按n越大算法越复杂来排的话:常数阶O(1)、对数阶O(logn)、线性阶O(n)、线性对数阶O(nlogn)、平方阶O(n²)、立方阶O(n³)、……k次方阶O(n的k次方)、指数阶O(2的n次方)。


   转载规则

《重新认识算法的时间复杂度字》GajAngels 采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可。