看动画轻松理解时间复杂度（二）

鹰兔牛熊眼 2019-01-17

展开全文

【作者简介】

程序员小吴，一个致力于用动画图解数据结构的程序员。LeetCodeAnimation作者，GitHub一万，连续一月占据Trending榜榜首。

上篇文章讲述了与复杂度有关的大 O 表示法和常见的时间复杂度量级，这篇文章来讲讲另外几种复杂度：递归算法的时间复杂度（recursive algorithm time complexity），最好情况时间复杂度（best case time complexity）、最坏情况时间复杂度（worst case time complexity）、平均时间复杂度（average case time complexity）和均摊时间复杂度（amortized time complexity）。

递归算法的时间复杂度

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

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

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

在前面的学习中，归并排序与快速排序都带有递归的思想，并且时间复杂度都是O(nlogn) ，但并不是有递归的函数就一定是 O(nlogn) 级别的。从以下两种情况进行分析。

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

二分查找法

 1int binarySearch(int arr[], int l, int r, int target){
 2    if( l > r ) return -1;
 3
 4    int mid = l + (r-l)/2; 
 5    if( arr[mid] == target ) return mid;  
 6    else if( arr[mid] > target ) 
 7    return binarySearch(arr, l, mid-1, target);    // 左边 
 8    else
 9    return binarySearch(arr, mid+1, r, target);   // 右边
10}

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

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

求和

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

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

求幂

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

递归深度为 logn，因为是求需要除以 2 多少次才能到底。

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

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

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

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

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

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

1 + 2 + 4 + 8 = 15

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

2^0 + 2^1 + 2^2 + …… + 2^n
= 2^(n+1) - 1
= O(2^n)

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

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

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

最好、最坏情况时间复杂度

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

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

1int find(int[] array, int n, int x) {
2  for (  int i = 0 ; i < n; i++) {
3    if (array[i] == x) {
4        return i;
5        break;
6    }
7  }
8  return -1;
9}

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

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

平均情况时间复杂度

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

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

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

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

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

均摊复杂度分析

我们通过一个动态数组的 push_back 操作来理解 均摊复杂度。

 1template <typename T>
 2class MyVector{
 3private:
 4    T* data;
 5    int size;       // 存储数组中的元素个数
 6    int capacity;   // 存储数组中可以容纳的最大的元素个数
 7    // 复杂度为 O(n)
 8    void resize(int newCapacity){
 9        T *newData = new T[newCapacity];
10        for( int i = 0 ; i < size ; i ++ ){
11              newData[i] = data[i];
12            }
13        data = newData;
14        capacity = newCapacity;
15    }
16public:
17    MyVector(){
18        data = new T[100];
19        size = 0;
20        capacity = 100;
21    }
22    // 平均复杂度为 O(1)
23    void push_back(T e){
24        if(size == capacity)
25            resize(2 * capacity);
26        data[size++] = e;
27    }
28    // 平均复杂度为 O(1)
29    T pop_back(){
30        size --;
31        return data[size];
32    }
33
34};