阅读 2219

看动画轻松理解时间复杂度(一)

原文链接:看动画轻松理解时间复杂度(一)

算法(Algorithm)是指用来操作数据、解决程序问题的一组方法。对于同一个问题,使用不同的算法,也许最终得到的结果是一样的,比如排序就有前面的十大经典排序和几种奇葩排序,虽然结果相同,但在过程中消耗的资源和时间却会有很大的区别,比如快速排序与猴子排序:)。

那么我们应该如何去衡量不同算法之间的优劣呢?

主要还是从算法所占用的「时间」和「空间」两个维度去考量。

  • 时间维度:是指执行当前算法所消耗的时间,我们通常用「时间复杂度」来描述。

  • 空间维度:是指执行当前算法需要占用多少内存空间,我们通常用「空间复杂度」来描述。

本小节将从「时间」的维度进行分析。

什么是大O

当看「时间」二字,我们肯定可以想到将该算法程序运行一篇,通过运行的时间很容易就知道复杂度了。

这种方式可以吗?当然可以,不过它也有很多弊端。

比如程序员小吴的老式电脑处理10w数据使用冒泡排序要几秒,但读者的iMac Pro 可能只需要0.1s,这样的结果误差就很大了。更何况,有的算法运行时间要很久,根本没办法没时间去完整的运行,还是比如猴子排序:)。

那有什么方法可以严谨的进行算法的时间复杂度分析呢?

有的!

「 远古 」的程序员大佬们提出了通用的方法:「 大O符号表示法 」,即 T(n) = O(f(n))

其中 n 表示数据规模 ,O(f(n))表示运行算法所需要执行的指令数,和f(n)成正比。

上面公式中用到的 Landau符号是由德国数论学家保罗·巴赫曼(Paul Bachmann)在其1892年的著作《解析数论》首先引入,由另一位德国数论学家艾德蒙·朗道(Edmund Landau)推广。Landau符号的作用在于用简单的函数来描述复杂函数行为,给出一个上或下(确)界。在计算算法复杂度时一般只用到大O符号,Landau符号体系中的小o符号、Θ符号等等比较不常用。这里的O,最初是用大写希腊字母,但现在都用大写英语字母O;小o符号也是用小写英语字母o,Θ符号则维持大写希腊字母Θ。

注:本文用到的算法中的界限指的是最低的上界。

常见的时间复杂度量级

我们先从常见的时间复杂度量级进行大O的理解:

  • 常数阶O(1)

  • 线性阶O(n)

  • 平方阶O(n²)

  • 对数阶O(logn)

  • 线性对数阶O(nlogn)

O(1)

无论代码执行了多少行,其他区域不会影响到操作,这个代码的时间复杂度都是O(1)

void swapTwoInts(int &a, int &b){
  int temp = a;
  a = b;
  b = temp;
}
复制代码

O(n)

在下面这段代码,for循环里面的代码会执行 n 遍,因此它消耗的时间是随着 n 的变化而变化的,因此可以用O(n)来表示它的时间复杂度。

int sum ( int n ){
   int ret = 0;
   for ( int i = 0 ; i <= n ; i ++){
      ret += i;
   }
   return ret;
}
复制代码

特别一提的是 c * O(n) 中的 c 可能小于 1 ,比如下面这段代码:

void reverse ( string &s ) {
    int n = s.size();
    for (int i = 0 ; i < n/2 ; i++){
      swap ( s[i] , s[n-1-i]);
    }
}
复制代码

O(n²)

当存在双重循环的时候,即把 O(n) 的代码再嵌套循环一遍,它的时间复杂度就是 O(n²) 了。

void selectionSort(int arr[],int n){
   for(int i = 0; i < n ; i++){
     int minIndex = i;
     for (int j = i + 1; j < n ; j++ )
       if (arr[j] < arr[minIndex])
           minIndex = j;
       
     swap ( arr[i], arr[minIndex]);
   }
}
复制代码

这里简单的推导一下

  • 当 i = 0 时,第二重循环需要运行 (n - 1) 次
  • 当 i = 1 时,第二重循环需要运行 (n - 2) 次
  • 。。。。。。

不难得到公式:

(n - 1) + (n - 2) + (n - 3) + ... + 0
= (0 + n - 1) * n / 2
= O (n ^2)

复制代码

当然并不是所有的双重循环都是 O(n²),比如下面这段输出 30n 次 Hello,五分钟学算法:)的代码。

void printInformation (int n ){
   for (int i = 1 ; i <= n ; i++)
        for (int j = 1 ; j <= 30 ; j ++)
           cout<< "Hello,五分钟学算法:)"<< endl;
}
复制代码

O(logn)

int binarySearch( int arr[], int n , int target){
  int l = 0, r = n - 1;
  while ( l <= r) {
    int mid = l + (r - l) / 2;
    if (arr[mid] == target) return mid;
    if (arr[mid] > target ) r = mid - 1;
    else l = mid + 1;
  }
  return -1;
}
复制代码

在二分查找法的代码中,通过while循环,成 2 倍数的缩减搜索范围,也就是说需要经过 log2^n 次即可跳出循环。

同样的还有下面两段代码也是 O(logn) 级别的时间复杂度。

  // 整形转成字符串
  string intToString ( int num ){
   string s = "";
   // n 经过几次“除以10”的操作后,等于0
   while (num ){
    s += '0' + num%10;
    num /= 10;
   }
   reverse(s)
   return s;
  }
复制代码
void hello (int n ) {
   // n 除以几次 2 到 1
   for ( int sz = 1; sz < n ; sz += sz) 
     for (int i = 1; i < n; i++)
        cout<< "Hello,五分钟学算法:)"<< endl;
}
复制代码

O(nlogn)

将时间复杂度为O(logn)的代码循环N遍的话,那么它的时间复杂度就是 n * O(logn),也就是了O(nlogn)。

void hello (){
  for( m = 1 ; m < n ; m++){
    i = 1;
    while( i < n ){
        i = i * 2;
    }
   }
}


复制代码

下一节将深入的对递归算法的复杂度进行分析,敬请期待:)

文章首发于公众号:五分钟学算法

关注下面的标签,发现更多相似文章
评论