十分鐘搞定時間複雜度（算法的時間複雜度）

我們假設計算機運作一行基礎代碼需要執行一次運算。

int aFunc(void) {

printf("Hello, World!\n");      //  需要執行 1 次
return 0;       // 需要執行 1 次           

}

那麼上面這個方法需要執行 2 次運算

int aFunc(int n) {

for(int i = 0; i<n; i++) {         // 需要執行 (n + 1) 次
    printf("Hello, World!\n");      // 需要執行 n 次
}
return 0;       // 需要執行 1 次           

這個方法需要 (n + 1 + n + 1) = 2n + 2 次運算。

我們把 算法需要執行的運算次數 用 輸入大小n 的函數 表示，即 T(n) 。

此時為了 估算算法需要的運作時間 和 簡化算法分析，我們引入時間複雜度的概念。

定義：存在常數 c 和函數 f(N)，使得當 N >= c 時 T(N) <= f(N)，表示為 T(n) = O(f(n)) 。

如圖：

當 N >= 2 的時候，f(n) = n^2 總是大于 T(n) = n + 2 的，于是我們說 f(n) 的增長速度是大于或者等于 T(n) 的，也說 f(n) 是 T(n) 的上界，可以表示為 T(n) = O(f(n))。

因為f(n) 的增長速度是大于或者等于 T(n) 的，即T(n) = O(f(n))，是以我們可以用 f(n) 的增長速度來度量 T(n) 的增長速度，是以我們說這個算法的時間複雜度是 O(f(n))。

算法的時間複雜度，用來度量算法的運作時間，記作: T(n) = O(f(n))。它表示随着 輸入大小n 的增大，算法執行需要的時間的增長速度可以用 f(n) 來描述。

顯然如果 T(n) = n^2，那麼 T(n) = O(n^2)，T(n) = O(n^3)，T(n) = O(n^4) 都是成立的，但是因為第一個 f(n) 的增長速度與 T(n) 是最接近的，是以第一個是最好的選擇，是以我們說這個算法的複雜度是 O(n^2) 。

那麼當我們拿到算法的執行次數函數 T(n) 之後怎麼得到算法的時間複雜度呢？

我們知道常數項對函數的增長速度影響并不大，是以當 T(n) = c，c 為一個常數的時候，我們說這個算法的時間複雜度為 O(1)；如果 T(n) 不等于一個常數項時，直接将常數項省略。

比如

第一個 Hello, World 的例子中 T(n) = 2，是以我們說那個函數(算法)的時間複雜度為 O(1)。

T(n) = n + 29，此時時間複雜度為 O(n)。

我們知道高次項對于函數的增長速度的影響是最大的。n^3 的增長速度是遠超 n^2 的，同時 n^2 的增長速度是遠超 n 的。 同時因為要求的精度不高，是以我們直接忽略低此項。

T(n) = n^3 + n^2 + 29，此時時間複雜度為 O(n^3)。

因為函數的階數對函數的增長速度的影響是最顯著的，是以我們忽略與最高階相乘的常數。

T(n) = 3n^3，此時時間複雜度為 O(n^3)。

綜合起來：如果一個算法的執行次數是 T(n)，那麼隻保留最高次項，同時忽略最高項的系數後得到函數 f(n)，此時算法的時間複雜度就是 O(f(n))。為了友善描述，下文稱此為 大O推導法。

由此可見，由執行次數 T(n) 得到時間複雜度并不困難，很多時候困難的是從算法通過分析和數學運算得到 T(n)。對此，提供下列四個便利的法則，這些法則都是可以簡單推導出來的，總結出來以便提高效率。

對于一個循環，假設循環體的時間複雜度為 O(n)，循環次數為 m，則這個

循環的時間複雜度為 O(n×m)。

void aFunc(int n) {

for(int i = 0; i < n; i++) {         // 循環次數為 n
    printf("Hello, World!\n");      // 循環體時間複雜度為 O(1)
}           

此時時間複雜度為 O(n × 1)，即 O(n)。

對于多個循環，假設循環體的時間複雜度為 O(n)，各個循環的循環次數分别是a, b, c...，則這個循環的時間複雜度為 O(n×a×b×c...)。分析的時候應該由裡向外分析這些循環。

for(int i = 0; i < n; i++) {         // 循環次數為 n
    for(int j = 0; j < n; j++) {       // 循環次數為 n
        printf("Hello, World!\n");      // 循環體時間複雜度為 O(1)
    }
}           

此時時間複雜度為 O(n × n × 1)，即 O(n^2)。

對于順序執行的語句或者算法，總的時間複雜度等于其中最大的時間複雜度。

// 第一部分時間複雜度為 O(n^2)
for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {
        printf("Hello, World!\n");
    }
}
// 第二部分時間複雜度為 O(n)
for(int j = 0; j < n; j++) {
    printf("Hello, World!\n");
}           

此時時間複雜度為 max(O(n^2), O(n))，即 O(n^2)。

對于條件判斷語句，總的時間複雜度等于其中 時間複雜度最大的路徑 的時間複雜度。

if (n >= 0) {
    // 第一條路徑時間複雜度為 O(n^2)
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            printf("輸入資料大于等于零\n");
        }
    }
} else {
    // 第二條路徑時間複雜度為 O(n)
    for(int j = 0; j < n; j++) {
        printf("輸入資料小于零\n");
    }
}           

時間複雜度分析的基本政策是：從内向外分析，從最深層開始分析。如果遇到函數調用，要深入函數進行分析。

最後，我們來練習一下

一. 基礎題

求該方法的時間複雜度

for (int i = 0; i < n; i++) {
    for (int j = i; j < n; j++) {
        printf("Hello World\n");
    }
}           

參考答案：

當 i = 0 時，内循環執行 n 次運算，當 i = 1 時，内循環執行 n - 1 次運算……當 i = n - 1 時，内循環執行 1 次運算。

是以，執行次數 T(n) = n + (n - 1) + (n - 2)……+ 1 = n(n + 1) / 2 = n^2 / 2 + n / 2。

根據上文說的 大O推導法 可以知道，此時時間複雜度為 O(n^2)。

二. 進階題

for (int i = 2; i < n; i++) {
    i *= 2;
    printf("%i\n", i);
}           

假設循環次數為 t，則循環條件滿足 2^t < n。

可以得出，執行次數t = log(2)(n)，即 T(n) = log(2)(n)，可見時間複雜度為 O(log(2)(n))，即 O(log n)。

三. 再次進階

long aFunc(int n) {

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

顯然運作次數，T(0) = T(1) = 1，同時 T(n) = T(n - 1) + T(n - 2) + 1，這裡的 1 是其中的加法算一次執行。

顯然 T(n) = T(n - 1) + T(n - 2) 是一個斐波那契數列，通過歸納證明法可以證明，當 n >= 1 時 T(n) < (5/3)^n，同時當 n > 4 時 T(n) >= (3/2)^n。

是以該方法的時間複雜度可以表示為 O((5/3)^n)，簡化後為 O(2^n)。

可見這個方法所需的運作時間是以指數的速度增長的。如果大家感興趣，可以試下分别用 1，10，100 的輸入大小來測試下算法的運作時間，相信大家會感受到時間複雜度的無窮魅力。