摘要訊息 : 通過列表法精確分析演算法的時間複雜度和空間複雜度.

0. 前言

在學習完《程式碼效能分析》和《漸近分析基礎》之後, 我們已經有能力對一個程式碼的時間複雜度和空間複雜度進行分析. 本篇文章將以《【演算法】名次排序法 (Ranking Sort)》為例, 對名次排序法的時間複雜度和空間複雜度進行分析.

更新紀錄 :

• 2022 年 6 月 2 日進行第一次更新和修正.

1. 非原地重排的名次排序法

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;
}

根據《程式碼效能分析》中的列表法, 我們進行列表 :

for(auto i {0}; i < n; ++i) { 的總程式步伐是 2n + 2+ 1 而不是 2n + 2 的原因就在於變數 i 需要初始化, 這裡有一個程式步伐前兩個表格是沒辦法列出來的. 下面幾個 for 迴圈在程式步伐上都是同樣的處理. 我要特別說明一下為什麼程式碼 for(auto j {0}; j < i; ++j) { 的頻率為 nO(n). 首先對於這個迴圈來說, 它的頻率隨著 i 的變化而變化, 那麼也就是說它的頻率為 2i + 2. 而 i 至少為 1, 至多為 n. 也就是說, 這個迴圈至少運作 1 次, 至多運作 n 次, 那麼頻率完全可以寫成 O(n). 但是外面還需要進行 n 次迴圈, 所以總體來說, 頻率就是 nO(n).

綜合表格中的信息, 根據《漸近分析基礎》中的定理 6, 即 Θ 記法比率定理, 我們可以得到 f(n) = 6nO(n) + 10n + 10 = \Theta(n^{2}). 因此, 非原地重排的名次排序的時間複雜度為 \Theta(n^{2}).

接著, 我們同樣列表分析非原地重排的名次排序的空間複雜度 :

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

2. 原地重排的名次排序法

#include <utility>

void ranking_sort(int array[], int size) {
    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 < n; ++i) {
        auto &save {rank[i]};
        while(save not_eq i) {
            std::swap(array[save], array[i]);
            std::swap(rank[save], save);
        }
    }
    delete[] rank;
}

我們直接通過比較非原地重排的名次排序法, 來分析 Code 2 的空間複雜度. 我們可以發現, 對比 Code 1, Code 2 的參數中少了一個 out, 因此這裡額外空間就會減少 n. 在 delete[] 之前的 for 迴圈中, 雖然我們宣告了額外的變數 save, 並且進行了兩次 std::swap 函式呼叫, 但是其對空間複雜度的級別並不會發生影響. 所以總體來說, 我們可以認為 Code 2 的額外空間為 n + 7, 即原地重排的名次排序法的空間複雜度仍然為 \Theta(n).

接著, 我們同樣列表分析原地重排的名次排序法的時間複雜度 :

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

最終, 我們可以得到原地重排的名次排序法的時間複雜度為 \Theta(n^{2}).