在學習完漸近數學和學會如何分析程式步伐之後, 我們可以針對一些已經給出的演算法資料結構中的一些操作分析它們的複雜度. 對於任何演算法或著資料結構的操作, 分析其複雜度是必要的. 一般在所有資料裡面, 複雜度分析都會在最後出現. 但是由於之前並沒有發布有關程式步伐分析和漸近分析的文章, 所以我也就沒有在最後進行複雜度分析. 在這篇文章中, 我們把已經發表文章的演算法和資料結構的複雜度都分析一邊

1. 【演算法】名次排序法 (Ranking Sort)

名次排序法有兩種, 一種是非原地重排的名次排序法, 另外一種是原地重排的名次排序法. 為了教會大家如何分析空間複雜度和時間複雜度, 我將會同時講述兩種名詞排序法的複雜度分析

由於大家剛剛開始進行分析, 所以我們首先使用列表的形式分析非原地重排的名次排序法, 分析其時間複雜度. 在之前的文章中, 我們將非原地重排的名次排序法分成了兩個函式, 此處為了方便分析, 我們將其合併為一個函式 :

void ranking_sort(const int array[], int size, int out[]) {
    auto rank {::new int[size]};
    for(auto i {0}; i < size; ++i) {
        rank[i] = 0;
    }
    for(auto i {1}; i < size; ++i) {
        for(auto j {0}; j < i; ++j) {
            if(array[j] > array[i]) {
                ++rank[j];
            }else {
                ++rank[i];
            }
        }
    }
    for(auto i {0}; i < size; ++i) {
        out[rank[i]] = array[i];
    }
    ::delete[] rank;
}

合併完成之後, 進行列表 (參考《程式碼效能分析》) :

陳述式 執行步伐 頻率 總程式步伐
void ranking_sort(const int array[], int n, int out[]) { 0 0 0
    auto rank {::new int[n]}; 1 1 1
    for(auto i {0}; i < n; ++i) { 1 2n + 2 2n + 2
        rank[i] = 0; 1 n n
    } 0 0 0
    for(auto i {1}; i < n; ++i) { 1 2n + 2 2n + 2
        for(auto j {0}; j < i; ++j) { 1 n^{2} + 3n + 2 n^{2} + 3n + 2
            if(array[j] > array[i]) { 1 \frac {n^{2} + n}{2} \frac {n^{2} + n}{2}
                ++rank[j]; 1 \frac {n^{2} + n}{4} \frac {n^{2} + n}{4}
            }else { 0 0 0
                ++rank[i]; 1 \frac {n^{2} + n}{4} \frac {n^{2} + n}{4}
            } 0 0 0
        } 0 0 0
    } 0 0 0
    for(auto i {0}; i < n; ++i) { 1 2n + 2 2n + 2
        out[rank[i]] = array[i]; 1 n n
    } 0 0 0
    ::delete[] rank; 1 1 1
} 0 0 0
程式步伐總計 n^{2} + 12n + 9

我要特別說明一下為什麼程式碼 for(auto j {0}; j < i; ++j) { 的頻率為 n^{2} + 3n + 2. 首先對於這個迴圈來說, 它的頻率隨著 i 的變化而變化, 那麼也就是說它的頻率為 2i + 2. 而 i 至少為 1, 至多為 n - 1. 也就是說, 這個迴圈至少運作 1 次, 至多運作 n 次, 那麼將每一次的頻率都加起來, 就得到了總的頻率 :

\sum \limits_{i = 1}^{n}(2i + 2) = n^{2} + 3n + 2

另外, 程式碼 ++rank[j]; 或著 ++rank[i]; 的執行步伐為 \frac {n^{2} + n}{4} 是因為每一次總有其中一句被運作, 另外一句被忽略. 因此, 我們乾脆將執行步伐平均地分配給它們. 另外, 包括外層的 if 陳述式, 它們每次都運作 i 次, 因此總計要被運作

\sum \limits_{i = 1}^{n}(i) = \frac {n^{2} + n}{2}

綜合表格中的信息, 根據大 O 記法定理 1 (參考《漸近分析基礎》), f(n) = n^{2} + 12n + 9 = O(n^{2}). 因此, 非原地重排的名次排序的時間複雜度為 O(n^{2}). 接著, 我們同樣列表分析非原地重排的名次排序的空間複雜度 :

陳述式 額外空間
void ranking_sort(const int array[], int n, int out[]) { 0
    auto rank {::new int[n]}; n
    for(auto i {0}; i < n; ++i) { 1
        rank[i] = 0; 0
    } 0
    for(auto i {1}; i < n; ++i) { 1
        for(auto j {0}; j < i; ++j) { 1
            if(array[j] > array[i]) { 0
                ++rank[j]; 0
            }else { 0
                ++rank[i]; 0
            } 0
        } 0
    } 0
    for(auto i {0}; i < n; ++i) { 1
        out[rank[i]] = array[i]; 0
    } 0
    ::delete[] rank; 0
} 0
程式步伐總計 n + 4

於是, 非原地重排的名次排序的空間複雜度為 O(n). 實際上, 非原地重排的名次排序並不需要 n + 4 那麼多的輔助空間, 因為用於迴圈的變數 ij, 當迴圈終結的時候它們就會被回收. 因此, 在同一時間, 按照我們上述的寫法, 輔助空間最多用到 n + 2. 但是也不排除有些人會把用於迴圈的變數獨立在迴圈之外宣告出來, 因此, 我們還是當它為 n + 4, 之後我也會這麼去計算空間複雜度

分析完非原地重排的名次排序後, 我們來分析原地重排的名次排序 :

陳述式 執行步伐 頻率 總程式步伐
void ranking_sort(const int array[], int n, int out[]) { 0 0 0
    auto rank {::new int[n]}; 1 1 1
    for(auto i {0}; i < n; ++i) { 1 2n + 2 2n + 2
        rank[i] = 0; 1 n n
    } 0 0 0
    for(auto i {1}; i < n; ++i) { 1 2n + 2 2n + 2
        for(auto j {0}; j < i; ++j) { 1 n^{2} + 3n + 2 n^{2} + 3n + 2
            if(array[j] > array[i]) { 1 \frac {n^{2} + n}{2} \frac {n^{2} + n}{2}
                ++rank[j]; 1 \frac {n^{2} + n}{4} \frac {n^{2} + n}{4}
            }else { 0 0 0
                ++rank[i]; 1 \frac {n^{2} + n}{4} \frac {n^{2} + n}{4}
            } 0 0 0
        } 0 0 0
    } 0 0 0
    for(auto i {0}; i < n; ++i) { 1 2n + 2 2n + 2
        auto &save {rank[i]} 1 n n
        while(save not_eq i) { 1 nO(n) O(n^{2})
            swap(array[save], array[i]); 3 nO(n) 3O(n^{2})
            swap(rank[save], save); 3 nO(n) 3O(n^{2})
        } 0 0 0
    } 0 0 0
    ::delete[] rank; 1 1 1
} 0 0 0
程式步伐總計 n^{2} + 7O(n^{2}) + 12n + 9

這裡, 我們說明一下最後的 while 迴圈中為什麼頻率是 nO(n) 而不是其它. 這是因為我們需要排序的元素總共有 n 個, 因此最多要交換 n - 1 次, 至少至少交換 1 次. 但是我們不知道它到底交換幾次, 因為現在元素都是未知的, 所以此處我們使用 O(n) 而不使用 nO(n) 表示次數上限, 且不為 0. 另外, 外層的 for 迴圈總計要運作 n 次, 所以內部的迴圈總計要運作 nO(n)

此時, 不知道你是否發現. 如果一個迴圈要運作 n 次, 其中 n 為實體特徵, 那麼程式的時間複雜度就增加 O(n); 如果迴圈裡還有一個迴圈, 那麼時間複雜度就增加了 O(n^{2}); ... 如果迴圈中途停止了, 或著運作次數少於 n 次, 程式的時間複雜度只增加 O(\log {n}). 雖然我們的程式無法避免迴圈, 但是我們希望它可以通過演算法的優化, 在迴圈中途就終結它, 使得我們程式的時間複雜度只增加 O(\log {n}). 二分搜尋法就是這樣的方法 :

2.【演算法】二分搜尋法 (Binary Search)

二分搜尋的程式碼只使用了一些輔助性的變數, 並且不論要搜尋的範圍有多大, 這些輔助性的變數數量保持不變, 所以其空間複雜度為 O(1). 程式碼中有一個迴圈, 對於順序搜尋來說, 最壞的情況是每一個都尋訪個邊, 因此順序搜尋的時間複雜度為 O(n). 但是二分搜尋至多只尋訪一半, 大多數情況下還沒到一半迴圈就被 break 終結了, 因此, 結合我們剛才總結的內容, 其複雜度降為 O(logn)

3. 【演算法】選擇排序法 (Selection Sort)

選擇排序法是原地重排的排序法, 因此只需要一些輔助性的變數, 空間複雜度為 O(1). 對於時間複雜度, 我們首先分析非及時終止的選擇排序法. 最內層的迴圈次數隨著傳入的實際大小的變化而變化, 那麼我們要和名次排序一樣進行求和. 外層的迴圈進行 n 次, 其中 n 為實體特徵. 那麼, 其複雜度和名次排序法相仿, 為 O(n^{2}). 再來分析及時終止的選擇排序法. 在最好的情況下, 尋訪完 n 個元素發現其有序, 直接終止. 此時複雜度為 \Theta(n). 但是在最壞的情況下, 從頭到尾都沒有被終止, 此時的複雜度為 \Theta(n^{2}). 因此, 即時是及時終止的選擇排序法, 其時間複雜度也為 O(n^{2}). 在最壞的情況下, 它不但沒有改進, 還比非及時終止的版本要慢一些

4. 【演算法】氣泡排序法 (Bubble Sort)

和選擇排序法類似, 氣泡排序法也只需要一些輔助性的變數, 空間複雜度為 O(1). 時間複雜度也和選擇排序法類似, 有兩層迴圈, 內層的迴圈次數取決於外層的迴圈標誌性變數, 因此不論是及時終止的版本還是非及時終止的版本, 其時間複雜度為 O(n^{2})

5. 【演算法】插入排序法 (Insertion Sort)

插入排序法也是同樣地, 空間複雜度為 O(1), 時間複雜度為 O(n^{2})

6. 【演算法】桶排序法 (Bucket Sort)

同排序法不再和前面的排序法類似, 因為它顯然大量使用了記憶體, 這個記憶體的用量甚至比實體特徵 n 還要大得多. 設 M 為要排序元素中最大的元素, m 為要排序元素中的最小元素. 我們至少要配置 r = M - m + 1 個連結串列 (其中, r 表示 range), 此處的空間複雜度已經達到了 O(r). 一般來說, 很少會出現實體特徵 n 恰好有 r 的情況. 而一般來說, 都是 n \ll r. 另外, 連結串列中可不是空的, 它至少需要額外配置 n 個節點用於保存元素, 此處的空間複雜度為 O(n). 因此, 同排序法的總空間複雜度為 O(n + r). 再來看看它的時間複雜度. 將 n 個元素影射到連結串列中, 此處的時間複雜度為 O(n). 然後把所有連結串列中的節點合併到一起, 這裡需要尋訪所有連結串列, 此處的時間複雜度為 O(r). 於是, 總的時間複雜度為 O(n + r). 但是實際上, 只有 O(n) 個連結串列中存在元素, 因為有些元素是相等的, 會被分配到同一個連結串列中. 而連結串列的合併的時間複雜度為 O(1), 實際用不了 O(n + r) 的時間. 因此, 我們大致認為, 桶排序法的時間複雜度為 O(n)

你可能還有疑問, 因為我呈現的程式碼中還有 before_last 的操作, 裡面也用到的迴圈, 為什麼沒有計入. 首先, 我們在進行時間複雜度分析的時候, 幾乎不會像開頭分析名次排序法那樣進行列表, 此時我們只需要對元素的操作進行分析就可以了. 另外, 這種輔助性的操作幾乎不可能出現複雜度比元素操作還高的情況, 也就是說即時出現它們的操作和元素的實體特徵相關, 它們的複雜度通常為 O(n) 甚至 O(logn). 而插入前向連結串列的操作需要經過前 k 個節點. 很顯然, 幾乎不可能存在 k = n 的情況, 也就是幾乎不存在全部元素都相等的情況. 就算是出現了, 其時間複雜度為 O(n), 最終的程式時間複雜度仍然為 O(n). 如果確實很不幸出現了 k = n 的情況, 那麼我們就更改存儲元素的資料結構, 將前向連結串列更改為連結串列, 這樣就將 before_last 的複雜度降低到了 O(1)

7. 【演算法】基數排序法 (Radix Sort)

有了桶排序法的經驗, 我們知道不需要分析函式 radix_sort_power 和 before_last 的複雜度, 因為它們不能對總的複雜度造成太大影響. 所以我們僅僅需要分析函式 radix_sort 的複雜度即可. 對於空間複雜度來說, 基數排序法相比於桶排序法就節省很多記憶體, 因為它僅僅需要配置基數 r 個大小的記憶體即可, 這個 r 表示 radix, 而不是之前的 range. 另外, 連結串列還需要額外 n 個大小的空間儲存元素, 於是總的空間複雜度為 O(r + n). 少了這麼多空間, 自然時間複雜度會多一些. 我們總共要進行 k 次桶排序, 其中 k 為最大元素的數碼數量 (比如 123455 個數碼, 09993 個數碼). 因此, 它的時間複雜度為 O(kn). 若且唯若 k = n 的時候, 其時間複雜度為 O(n^{2})

我們發現, 桶排序法和基數排序法的空間用量比較大, 但是時間複雜度被降低了. 這是典型的空間換時間的思想, 這在演算法的設計中非常有用. 當然你也看到了, 名次排序法需要額外的 O(n) 的空間, 但是它的時間複雜度並沒有被降低到 O(n \log {n}) 或著 O(n). 因此, 演算法如果涉及不當, 空間就不一定總能夠換取時間

8. 資料結構

我們目前講述過的重構資料結構 (沒有重構過的我們暫時不分析) 有 : 向量、前向連結串列、連結串列、堆疊、佇列、雙向佇列和陣列. 我們選取一些經典的操作來講述

向量的插入要分兩種情況, 刪除也是類似地, 一種是在最後插入, 此時在空間足夠的情況下複雜度為 \Theta(1). 此處的複雜度就是單指時間複雜度, 對於存儲元素的資料結構分析空間複雜度毫無意義. 如果不是在最後插入, 那麼就要移動或著複製插入位置之後的元素, 此時的複雜度為 \Omega(1), 最高為 O(n). 其中, n 為資料結構中目前存儲的元素數量. 對於連結串列來說, 如果到達了指定位置或著使用了疊代器, 那麼插入總是 \Theta(1) 的複雜度, 刪除也是這樣. 對於雙向佇列來說, 不論在頭部還是尾部插入, 其複雜度都為 \Theta(1), 在中間插入的情況和向量差不多. 因為雙向佇列可以向前移動, 所以一半只要不是正好在正中間插入, 在演算法優化過後, 其複雜度稍低於向量的插入複雜度

 

最後, 在經過這篇文章之後, 我相信大家已經學會了複雜度的分析方法. 在之後的資料結構和演算法系列的文章中, 我將直接把複雜度分析放在文章最後, 而不是獨立寫一篇文章