上篇文章講述了與復(fù)雜度有關(guān)的大 O 表示法和常見的時(shí)間復(fù)雜度量級(jí)，這篇文章來講講另外幾種復(fù)雜度： 遞歸算法的時(shí)間復(fù)雜度（recursive algorithm time complexity），最好情況時(shí)間復(fù)雜度（best case time complexity）、最壞情況時(shí)間復(fù)雜度（worst case time complexity）、平均時(shí)間復(fù)雜度（average case time complexity）和均攤時(shí)間復(fù)雜度（amortized time complexity）。

遞歸算法的時(shí)間復(fù)雜度

如果遞歸函數(shù)中，只進(jìn)行一次遞歸調(diào)用，遞歸深度為depth；

在每個(gè)遞歸的函數(shù)中，時(shí)間復(fù)雜度為T；

則總體的時(shí)間復(fù)雜度為O(T * depth)。

在前面的學(xué)習(xí)中，歸并排序 與 快速排序 都帶有遞歸的思想，并且時(shí)間復(fù)雜度都是O(nlogn) ，但并不是有遞歸的函數(shù)就一定是 O(nlogn) 級(jí)別的。從以下兩種情況進(jìn)行分析。

① 遞歸中進(jìn)行一次遞歸調(diào)用的復(fù)雜度分析

二分查找法

image

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 ] 范圍中去查找目標(biāo)的位置，如果中間的元素 arr[mid] 不是 target，那么判斷 arr[mid]是比 target 大 還是 小 ，進(jìn)而再次調(diào)用 binarySearch這個(gè)函數(shù)。

在這個(gè)遞歸函數(shù)中，每一次沒有找到target時(shí)，要么調(diào)用 左邊 的 binarySearch函數(shù)，要么調(diào)用 右邊 的 binarySearch函數(shù)。也就是說在此次遞歸中，最多調(diào)用了一次遞歸調(diào)用而已。根據(jù)數(shù)學(xué)知識(shí)，需要log2n次才能遞歸到底。因此，二分查找法的時(shí)間復(fù)雜度為 O(logn)。

求和

image

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

在這段代碼中比較容易理解遞歸深度隨輸入 n 的增加而線性遞增，因此時(shí)間復(fù)雜度為 O (n)。

求冪

image

//遞歸深度：logn
//時(shí)間復(fù)雜度：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;
}

遞歸深度為 logn，因?yàn)槭乔笮枰?2 多少次才能到底。

② 遞歸中進(jìn)行多次遞歸調(diào)用的復(fù)雜度分析

遞歸算法中比較難計(jì)算的是多次遞歸調(diào)用。

先看下面這段代碼，有兩次遞歸調(diào)用。

// O(2^n) 指數(shù)級(jí)別的數(shù)量級(jí)，后續(xù)動(dòng)態(tài)規(guī)劃的優(yōu)化點(diǎn)
int f(int n){
 if (n == 0) return 1;
 return f(n-1) + f(n - 1);
}

image

遞歸樹中節(jié)點(diǎn)數(shù)就是代碼計(jì)算的調(diào)用次數(shù)。

比如 當(dāng) n = 3 時(shí)，調(diào)用次數(shù)計(jì)算公式為

1 + 2 + 4 + 8 = 15

一般的，調(diào)用次數(shù)計(jì)算公式為

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

image

與之有所類似的是 歸并排序 的遞歸樹，區(qū)別點(diǎn)在于

• 1. 上述例子中樹的深度為 n，而 歸并排序 的遞歸樹深度為logn。
• 2. 上述例子中每次處理的數(shù)據(jù)規(guī)模是一樣的，而在 歸并排序 中每個(gè)節(jié)點(diǎn)處理的數(shù)據(jù)規(guī)模是逐漸縮小的

因此，在如 歸并排序 等排序算法中，每一層處理的數(shù)據(jù)量為 O(n) 級(jí)別，同時(shí)有 logn 層，時(shí)間復(fù)雜度便是 O(nlogn)。

最好、最壞情況時(shí)間復(fù)雜度

image

最好、最壞情況時(shí)間復(fù)雜度指的是特殊情況下的時(shí)間復(fù)雜度。

動(dòng)圖表明的是在數(shù)組 array 中尋找變量 x 第一次出現(xiàn)的位置，若沒有找到，則返回 -1；否則返回位置下標(biāo)。

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

在這里當(dāng)數(shù)組中第一個(gè)元素就是要找的 x 時(shí)，時(shí)間復(fù)雜度是 O(1)；而當(dāng)最后一個(gè)元素才是 x 時(shí)，時(shí)間復(fù)雜度則是 O(n)。

最好情況時(shí)間復(fù)雜度就是在最理想情況下執(zhí)行代碼的時(shí)間復(fù)雜度，它的時(shí)間是最短的；最壞情況時(shí)間復(fù)雜度就是在最糟糕情況下執(zhí)行代碼的時(shí)間復(fù)雜度，它的時(shí)間是最長(zhǎng)的。

平均情況時(shí)間復(fù)雜度

最好、最壞時(shí)間復(fù)雜度反應(yīng)的是極端條件下的復(fù)雜度，發(fā)生的概率不大，不能代表平均水平。那么為了更好的表示平均情況下的算法復(fù)雜度，就需要引入平均時(shí)間復(fù)雜度。

平均情況時(shí)間復(fù)雜度可用代碼在所有可能情況下執(zhí)行次數(shù)的加權(quán)平均值表示。

還是以 find 函數(shù)為例，從概率的角度看， x 在數(shù)組中每一個(gè)位置的可能性是相同的，為 1 / n。那么，那么平均情況時(shí)間復(fù)雜度就可以用下面的方式計(jì)算：

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

find 函數(shù)的平均時(shí)間復(fù)雜度為 O(n)。

均攤復(fù)雜度分析

我們通過一個(gè)動(dòng)態(tài)數(shù)組的 push_back 操作來理解 均攤復(fù)雜度。

image

template <typename T>
class MyVector{
private:
    T* data;
    int size;       // 存儲(chǔ)數(shù)組中的元素個(gè)數(shù)
    int capacity;   // 存儲(chǔ)數(shù)組中可以容納的最大的元素個(gè)數(shù)
    // 復(fù)雜度為 O(n)
    void resize(int newCapacity){
        T *newData = new T[newCapacity];
        for( int i = 0 ; i < size ; i ++ ){
              newData[i] = data[i];
            }
        data = newData;
        capacity = newCapacity;
    }
public:
    MyVector(){
        data = new T[100];
        size = 0;
        capacity = 100;
    }
    // 平均復(fù)雜度為 O(1)
    void push_back(T e){
        if(size == capacity)
            resize(2 * capacity);
        data[size++] = e;
    }
    // 平均復(fù)雜度為 O(1)
    T pop_back(){
        size --;
        return data[size];
    }

};

push_back實(shí)現(xiàn)的功能是往數(shù)組的末尾增加一個(gè)元素，如果數(shù)組沒有滿，直接往后面插入元素；如果數(shù)組滿了，即 size == capacity ，則將數(shù)組擴(kuò)容一倍，然后再插入元素。

例如，數(shù)組長(zhǎng)度為 n，則前 n 次調(diào)用 push_back 復(fù)雜度都為 O(1) 級(jí)別；在第 n + 1 次則需要先進(jìn)行 n 次元素轉(zhuǎn)移操作，然后再進(jìn)行 1 次插入操作，復(fù)雜度為 O(n)。

因此，平均來看：對(duì)于容量為 n 的動(dòng)態(tài)數(shù)組，前面添加元素需要消耗了 1 * n 的時(shí)間，擴(kuò)容操作消耗 n 時(shí)間 ，
總共就是 2 * n 的時(shí)間，因此均攤時(shí)間復(fù)雜度為 O(2n / n) = O(2)，也就是 O(1) 級(jí)別了。

可以得出一個(gè)比較有意思的結(jié)論：一個(gè)相對(duì)比較耗時(shí)的操作，如果能保證它不會(huì)每次都被觸發(fā)，那么這個(gè)相對(duì)比較耗時(shí)的操作，它所相應(yīng)的時(shí)間是可以分?jǐn)偟狡渌牟僮髦衼淼摹?/p>

image