Algorithm

【Algorithm】算法的时间复杂度（Time Complexity）

Posted by 西维蜀黍 on 2019-07-27, Last Modified on 2023-09-02

常见的时间复杂度量级

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

  • 常数阶O(1)

  • 对数阶$O(log_2n)$

  • 线性阶O(n)

  • 线性对数阶$On(log_2n)$

  • 平方阶$O(n^2)$

  • 指数阶$O(2^n)$

复杂度 标记符号 描述
常量（Constant） $O(1) $ 操作的数量为常数，与输入的数据的规模无关。n = 1,000,000 -> 1-2 operations
对数（Logarithmic） $O(log_2n)$ 操作的数量与输入数据的规模 n 的比例是 log2 (n)。n = 1,000,000 -> 30 operations
线性（Linear） $O(n)$ 操作的数量与输入数据的规模 n 成正比。n = 10,000 -> 5000 operations
平方（Quadratic） $O(n^2)$ 操作的数量与输入数据的规模 n 的比例为二次平方。n = 500 -> 250,000 operations
立方（Cubic） $O(n^3)$ 操作的数量与输入数据的规模 n 的比例为三次方。n = 200 -> 8,000,000 operations
指数（Exponential） $O(2^n)$、$O(k^n)$、$O(n!)$ 指数级的操作，快速的增长。n = 20 -> 1048576 operations

列举了几种常见的算法时间复杂度的比较（又小到大）：$O(1)$（常数阶） < $O(log_2n)$（对数阶） < $O(n)$（线性阶） < $O(n2)$（平方阶） < $O(n3)$（立方阶） < $O(2^n)$ (指数阶)。

通常将以 10 为底的对数叫做常用对数。为了简便，N 的常用对数 log10 N 简写做 lg N，例如 log10 5 记做 lg 5。

通常将以无理数 e 为底的对数叫做自然对数。为了方便，N 的自然对数 loge N 简写做 ln N，例如 loge 3 记做 ln 3。

在算法导论中，采用记号 $lg n = log_2n$ ，也就是以 2 为底的对数。改变一个对数的底只是把对数的值改变了一个常数倍，所以当不在意这些常数因子时，我们将经常采用 “lg n"记号，就像使用 O 记号一样。计算机工作者常常认为对数的底取 2 最自然，因为很多算法和数据结构都涉及到对问题进行二分。

而通常时间复杂度与运行时间有一些常见的比例关系：

复杂度 10 20 50 100 1000 10000 100000
$O(1)$ <1s <1s <1s <1s <1s <1s <1s
$O(log_2(n))$ <1s <1s <1s <1s <1s <1s <1s
$O(n)$ <1s <1s <1s <1s <1s <1s <1s
$O(n*log_2(n))$ <1s <1s <1s <1s <1s <1s <1s
$O(n^2)$ <1s <1s <1s <1s <1s 2s 3-4 min
$O(n^3)$ <1s <1s <1s <1s 20s 5 hours 231 days
$O(2^n)$ <1s <1s 260 days hangs hangs hangs hangs
$O(n!)$ <1s hangs hangs hangs hangs hangs hangs
$O(n^n)$ 3-4 min hangs hangs hangs hangs hangs hangs

时间复杂度的计算

计算一个算法的时间复杂度，不可能把所有的算法都编写出实际的程序出来让计算机跑，这样会做很多无用功，效率太低。实际采用的方法是估算算法的时间复杂度。

在学习C语言的时候讲过，程序由三种结构构成：顺序结构、分支结构和循环结构。顺序结构和分支结构中的每段代码只运行一次；循环结构中的代码的运行时间要看循环的次数。

由于是估算算法的时间复杂度，相比而言，循环结构对算法的执行时间影响更大。所以，算法的时间复杂度，主要看算法中使用到的循环结构中代码循环的次数（称为“频度”）。次数越少，算法的时间复杂度越低。

例如：

//a) 
++x; s=0;

//b) 
for (int i=1; i<=n; i++) { 
	++x; 
  s+=x; 
}

//c) 
for (int i=1; i<=n; i++) { 
  for (int j=1; i<=n; j++) { 
    ++x; 
    s+=x; 
  } 
}

上边这个例子中，a 代码的运行了 1 次，b 代码的运行了 n 次，c 代码运行了 n*n 次。

时间复杂度的表示

算法的时间复杂度的表示方式为：O(频度)，这种表示方式称为大“O”记号法（Big O Notation）。

注意，是大写的字母O，不是数字0。

对于上边的例子而言，a 的时间复杂度为$O(1)$，b 的时间复杂度为$O(n)$，c 的时间复杂度为为$O(n^2)$。

如果a、b、c组成一段程序，那么算法的时间复杂度为$O(n^2+n+1)$。但这么表示是不对的，还需要对$n^2+n+1$ 进行简化。

简化的过程总结为3步：

  • 去掉运行时间中的所有加法常数（例如 $n^2+n+1$，直接变为 $n^2+n$）。
  • 只保留最高项（$n^2+n$ 变成 $n^2$）。
  • 如果最高项存在但是系数不是1，去掉系数（$n^2$ 系数为 1）。

所以，最终a、b和c合并而成的代码的时间复杂度为$O(n^2)$。

时间复杂度计算示例

常数阶 - $O(1)$

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

void swapTwoInts(int &a, int &b){
  int temp = a;
  a = b;
  b = temp;
}

对数阶 - $O(log_2n)$

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 倍数的缩减搜索范围，也就是说需要经过 $log_2n$ 次即可跳出循环。

线性阶 - $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;
}

$O(nlog_2n)$

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

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

平方阶 - $O(n^2)$

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

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^3)$

decimal Sum3(int n)
{
  decimal sum = 0;
  for (int a = 0; a < n; a++)
    for (int b = 0; b < n; b++)
      for (int c = 0; c < n; c++)
        sum += a * b * c;
  return sum;
}

这里，给定规模 n，则基本步骤的执行数量约为 n*n*n ，所以算法复杂度为 $O(n^3)$。

指数阶 - $O(2^n)$

斐波那契数列：

  • Fib(0) = 0
  • Fib(1) = 1
  • Fib(n) = Fib(n-1) + Fib(n-2)

F() = 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 …

int Fibonacci(int n)
{
  if (n <= 1)
    return n;
  else
    return Fibonacci(n - 1) + Fibonacci(n - 2);
}

这里，给定规模 n，计算 Fib(n) 所需的时间为计算 Fib(n-1) 的时间和计算 Fib(n-2) 的时间的和。

T(n<=1) = O(1)

T(n) = T(n-1) + T(n-2) + O(1)

                     fib(5)   
                 /             \     
           fib(4)                fib(3)   
         /      \                /     \
     fib(3)      fib(2)         fib(2)    fib(1)
    /     \        /    \       /    \

通过使用递归树的结构描述可知算法复杂度为 $O(2^n)$。

递归算法的时间复杂度（recursive algorithm time complexity）

如果递归函数中，只进行一次递归调用，递归深度为depth；

在每个递归的函数中，时间复杂度为T；

则总体的时间复杂度为O(T * depth)。

我们知道，归并排序与快速排序都带有递归的思想，并且时间复杂度都是$O(nlog_2n)$，但并不是有递归的函数就一定是 $O(nlog_2n)$ 级别的。

1 递归中进行一次递归调用的复杂度分析

二分查找法

int binarySearch(int arr[], int l, int r, int target){
    if( l > r ) return -1;
    
    int mid = l + (r-l)/2; 
    if( arr[mid] == target ) 
      return mid;  
    else if( arr[mid] > target ) 
    	return binarySearch(arr, l, mid-1, target);    // 左边 
    else
    	return binarySearch(arr, mid+1, r, target);   // 右边
}

比如在这段二分查找法的代码中，每次在 [ l , r ] 范围中去查找目标的位置，如果中间的元素 arr[mid] 不是 target，那么判断 arr[mid]是比 target 大 还是 小 ，进而再次调用 binarySearch这个函数。

在这个递归函数中，每一次没有找到target时，要么调用 左边 的 binarySearch函数，要么调用 右边 的 binarySearch函数。也就是说在此次递归中，最多调用了一次递归调用而已。根据数学知识，需要$log_2n$次才能递归到底。因此，二分查找法的时间复杂度为 $O(log_2n)$。

求和

int sum (int n) {
  if (n == 0) return 0;
  return n + sum( n - 1 )
}

在这段代码中比较容易理解递归深度随输入 n 的增加而线性递增，因此时间复杂度为 O (n)。

求幂

//递归深度：logn
//时间复杂度：O(logn)
double pow( double x, int n){
  if (n == 0) return 1.0;
  
  double t = pow(x,n/2);
  if (n %2) return x*t*t;
  return t * t;
}

递归深度为$O(log_2n)$，因为是求需要除以 2 多少次才能到底。

2 递归中进行多次递归调用的复杂度分析

递归算法中比较难计算的是多次递归调用。

先看下面这段代码，有两次递归调用。

// O(2^n) 指数级别的数量级，后续动态规划的优化点
int f(int n){
 if (n == 0) return 1;
 return f(n-1) + f(n - 1);
}

递归树中节点数就是代码计算的调用次数。

比如 当 n = 3 时，调用次数计算公式为

1 + 2 + 4 + 8 = 15

一般的，调用次数计算公式为

20 + 21 + 22 + …… + 2n = 2(n+1) - 1 = O(2n)

与之有所类似的是 归并排序 的递归树，区别点在于

  • 上述例子中树的深度为 n，而 归并排序 的递归树深度为logn。
  • 上述例子中每次处理的数据规模是一样的，而在 归并排序 中每个节点处理的数据规模是逐渐缩小的

因此，在如 归并排序 等排序算法中，每一层处理的数据量为 O(n) 级别，同时有 $O(log_2n)$ 层，时间复杂度便是 $O(nlog_2n)$。

最好、最坏情况时间复杂度（Worst case time complexity）

最好、最坏情况时间复杂度指的是特殊情况下的时间复杂度。

动图表明的是在数组 array 中寻找变量 x 第一次出现的位置，若没有找到，则返回 -1；否则返回位置下标。

int find(int[] array, int n, int x) {
  for (  int i = 0 ; i < n; i++) {
    if (array[i] == x) {
        return i;
        break;
    }
  }
  return -1;
}

在这里当数组中第一个元素就是要找的 x 时，时间复杂度是 O(1)；而当最后一个元素才是 x 时，时间复杂度则是 O(n)。

最好情况时间复杂度就是在最理想情况下执行代码的时间复杂度，它的时间是最短的；最坏情况时间复杂度就是在最糟糕情况下执行代码的时间复杂度，它的时间是最长的。

平均情况时间复杂度（Average case time complexity）

最好、最坏时间复杂度反应的是极端条件下的复杂度，发生的概率不大，不能代表平均水平。那么为了更好的表示平均情况下的算法复杂度，就需要引入平均时间复杂度。

平均情况时间复杂度可用代码在所有可能情况下执行次数的加权平均值表示。

还是以 find 函数为例，从概率的角度看， x 在数组中每一个位置的可能性是相同的，为 1 / n。那么，那么平均情况时间复杂度就可以用下面的方式计算：

((1 + 2 + … + n) / n + n) / 2 = (3n + 1) / 4

find 函数的平均时间复杂度为 O(n)。

拿时间换空间，用空间换时间

算法的时间复杂度和空间复杂度是可以相互转化的。

谷歌浏览器相比于其他的浏览器，运行速度要快。是因为它占用了更多的内存空间，以空间换取了时间。

例如判断某个年份是否为闰年时，如果想以时间换取空间，算法思路就是：当给定一个年份时，判断该年份是否能被4或者400整除，如果可以，就是闰年。

如果想以空间换时间的话，判断闰年的思路就是：把所有的年份先判断出来，存储在数组中（年份和数组下标对应），如果是闰年，数组值是1，否则是0；当需要判断某年是否为闰年时，直接看对应的数组值是1还是0，不用计算就可以马上知道。

Reference

FEATURED TAGS
algorithm algorithmproblem architecturalpattern architecture aws c# cachesystem codis compile concurrentcontrol database dataformat datastructure debug design designpattern distributedsystem django docker domain engineering freebsd git golang grafana hackintosh hadoop hardware hexo http hugo ios iot java javaee javascript kafka kubernetes linux linuxcommand linuxio lock macos markdown microservices mysql nas network networkprogramming nginx node.js npm oop openwrt operatingsystem padavan performance programming prometheus protobuf python redis router security shell software testing spring sql systemdesign truenas ubuntu vmware vpn windows wmware wordpress xml zookeeper
FRIENDS

TOC