摘要訊息 : 如何正確地從理論和實際的角度分析程式碼的空間複雜度和時間複雜度?

0. 前言

如果我們寫出某個程式碼或者實作了某一個演算法, 我們必須合理分析這個程式碼所使用的空間和程式碼運作所需要的時間是否合理. 例如, 我們現在想要實作一個調查問卷網頁, 這個網頁的載入用了一個小時而且耗盡了使用者電腦的記憶體, 這就不太合理. 有時候, 我們為了追求極致的程式效能, 也需要通過分析程式碼所使用的空間和運作時間來進行優化. 我們一般稱一個程式運作所需要的時間和空間大小為程式效能.

更新紀錄 :

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

1. 分析方法

要測量一個程式的運作效能, 我們一般使用理論分析的方法和實驗的方法. 理論分析的方法是從理論上得到一個程式的複雜性, 這個複雜性通常使用公式來表示. 有了這個公式之後, 我們就可以對比相同功能的不同程式, 從數學分析的角度來分析這些程式運作效能不同的根本原因. 而實驗的方法是最常用的, 因為對於一些大型程式, 從理論上去分析是不現實的, 也是很浪費時間的. 這個時候, 我們通常使用實驗的方法來測試程式的正確性同時記錄程式運作所需要的空間和時間.

2. 空間複雜度

空間複雜度是指一個程式運作所需要的空間大小, 由程式碼, 數據和環境堆疊佔用的容量之和所構成. 程式碼所佔用的容量取決於把程式轉化成機器語言的編碼器, 在編碼時編碼器的選項和目標作業系統甚至電腦硬體. 數據所佔用的容量是由所有的常數和變數所需的儲存空間, 另外還包括那些動態物件所需要的儲存空間總和. 在函式中呼叫另外一個函式可能導致當前函式需要暫停運作, 這個時候就需要儲存當前函式暫停的時候的所有狀態, 包括運作到哪裡, 各個變數和參數的值. 這些狀態所需要的儲存空間構成了環境堆疊佔用的容量.

一個程式所要佔有的容量空間取決於若干因素, 有些因素在編寫程式碼的時候是無法預知的. 另外, 就算是這些因素已經確定了下來, 但是我們也無法精確地分析出一個程式在運作時所需要的容量大小. 例如, 當程式長時間未使用的時候, 它所佔用的記憶體可能很小, 因為大部分資料都被作業系統從記憶體中轉移到硬碟上了. 那轉移的那一部分大小, 我們沒辦法精確計算的, 因為作業系統可能在其中增加了一些輔助性的資料, 這些輔助性資料甚至隨著作業系統版本不同而不同. 這就為我們分析程式的空間複雜度帶來了極大的麻煩.

一個程式要處理的問題都有一些特徵, 這些特徵可以影響甚至決定程式運作時所需要的數據空間. 考慮一個排序演算法, 排序演算法要處理的是一個未知的序列, 而這個未知序列的大小在總體上影響著這個排序演算法運作時所需要的空間大小. 若需要排序的序列有 n 個元素, 那麼它的實體特徵就為 n. 再考慮兩個 m 行 n 列的矩陣相加的程式, 那麼這個相加程式的實體特徵為 m 和 n.

相對來說, 程式碼所佔用的空間大小並不是太受到實體特徵的影響. 常數和簡單變數所佔有的容量也和實體特徵沒有特別大的關係. 當你的程式碼違背了這個斷言, 你可能需要考慮重寫你的程式碼或著選擇另外一種資料結構. 除此之外, 某一些動態配置的大小也可以不依賴於實體特徵, 比如環境堆疊的大小. 但是有個例外, 如果函式是遞迴的, 那麼實體特徵通常 (但不總是) 會影響環境堆疊的容量大小. 遞迴函式所需要的堆疊容量通常稱為遞迴堆疊空間, 其大小依賴於拘於變數和函式參數所需要的容量大小以及遞迴的深度, 有時候編碼器也會影響遞迴堆疊空間.

綜上所述, 我們可以將一個程式 P 運作時所需要的空間大小分成兩個部分 :

• 固定部分 : 它獨立於實體特徵, 通常包含程式碼本身、簡單變數和常數的空間等. 固定部分所佔用的大小通常為某個常數 c;
• 可變部分 : 主要是指動態配置的空間和遞迴堆疊空間, 前者一定程度上依賴於實體特徵, 後者主要依賴於實體特徵. 由於可變部分依賴於實體特徵, 那麼其所佔用的空間大小可以表示為 S_{P}(n). 其中, n 是實體特徵.

於是, 任意程式 P 所需要的空間可以表示為 \displaystyle {S_{P}(n) + c}.

如果想要精確分析程式的空間複雜度, 還要考慮編碼器編碼時產生的臨時變數所佔用的容量. 除了遞迴函式之外, 這些容量通常與實體特徵無關而與編碼器直接相關. 例如, 帶有虛擬函式的類別, 編碼器通常要插入額外的一些數據, 這些數據我們是無法看到的. 根據上面的討論結果, 精確地分析程式的空間複雜度通常不太可能. 於是要分析一個程式的空間複雜度, 我們將目標集中於計算 S_{P}(n) 上. 對於任意給定的問題, 我們首先要確定哪些實體特徵可以用來估算空間的需求. 對於實體特徵為 n 的程式, 若程式並不需要動態配置記憶體空間且函式不是遞迴函式, 那麼有 \displaystyle {S_{P}(n) = n + c_{0}}. 其中, c_{0} 是一些輔助性變數使用的空間之和. 例如

void f(int arr[], int n) {
    auto rank {new int[n] {}};
    for(int i {}; i < n; ++i) {
        rank[i] = arr[i] + i;
    }
    delete[] rank;
}

在呼叫函式 f 的時候, 如果把單位限定至位元組, 那麼在 64 位元的作業系統上, 有 S_{f}(n) = 8n + 24. 因為函式 f 的參數 arr 會退化為指標, 其 sizeof 值為 8, 另外一個參數 n 的 sizeof 值為 4. 除此之外, 參數 arr 內部還儲存了 n 個 int 型別的元素, 共佔了 4n 位元組. 函式內, 變數 rank 是一個指標, 和參數 arr 一樣佔了 8 位元組. 變數 rank 指向的記憶體空間中, 還儲存了 n 個 int 型別的元素, 此處有 4n 位元組. 在 for 迴圈中, 宣告了一個變數 i, 佔了 4 位元組. 把這些加起來可以得到 \displaystyle {S_{f}(n) = 8 + 4 + 4n + 8 + 4n + 4 = 8n + 24}. 這裡, c_{0} = 24

但是一般來說, 我們不會把分析精確到位元組那麼細, 我們會視所有變數都為 1, 有幾個變數, c_{0} 的值就是多少. 此時, 我們有 \displaystyle {S_{f}(n) = 2n + 4}. 不同的人會有不同的標準. 為了統一起見, 接下來我們都將視所有變數都為 1.

再考慮一個帶有遞迴的程式碼 :

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

我們首先考慮的不是直接去計算 S_{s}(n), 而是先像對待非遞迴那樣分析. 顯然, 函式 s 沒有宣告任何變數, 僅僅有一個參數, 因此在沒有遞迴, 即 n = 0 或者 n = 1 的情況下, 有 S_{s}(n) = 1. 對於任意 n > 1, 第一次呼叫的時候, 函式會在 return 陳述式暫停, 此時需要儲存參數 n 的值和當前運作暫停的地方, 然後呼叫 s(n - 1). 這個過程總共要進行 n 次直到 n = 1, 所以 S_{s}(n) = 2n. 其中, 2 表示了儲存 n 的時候用的空間和儲存函式暫停處所要的空間. 綜上所述, 有 \displaystyle {S_{s}(n) = \begin {cases} 1 & {n = 0, 1} \\ 2n & {n > 1}. \end {cases}}

3. 時間複雜度

一個程式 P 所需要的時間是編碼的時間和運作的時間之和. 編碼時間通常和實體特徵的關係不大, 而一個程式通過一次編碼可以反覆運作多次, 因此編碼時間自然就不是關注的重點, 關注的重點是運作時間. 運作時間通常使用 t_{P}(n) 來表示. 其中, n 為實體特徵. 我們在構思一個程式的時候, 對於可能影響 t_{P} 值的因素還不是很清楚, 因此僅僅能對其值進行估算. 如果我們了解編碼器, 那麼通常可以知道那些基本操作的時間. 例如加減乘除, 指標運算, 解參考和函式呼叫等等. 但是實際上, 並不是所有數字的加減乘除所需要的時間都是相同的, 這取決於運算元的型別. 例如, 如果運算元是 unsigned int 型別, 它的基本運算可能比 float 型別更快. 甚至這些計算的時間還可能取決於作業系統和裝置. 類似於空間複雜度, 我們幾乎沒辦法精確地分析一個程式的時間複雜度, 只能估算運作時間 :

1. 找出一個或著多個關鍵操作, 確定其運作時間;
2. 確定程式的總步伐.

像 a * b 或者 a + b 這樣的操作, 我們將其時間步伐視為 1. 所謂時間步伐 (time step), 簡稱為步伐 (step), 它可以大概定義為一個語法上或著語意上的程式片段, 這個片段運作的時間獨立於實體特徵. 在 C++ 中, 宣告變數, 基本運算, 指標運算, 函式呼叫和條件判斷都可以視為一個時間步伐. 但是這個定義是模糊的, 例如我們可以將 a = x + y + z 的運算視為一個步伐, 也可以視為三個步伐 (x + y 是一個步伐, (x + y) + z 是一個步伐, 將運算結果指派給 a 又是一個步伐). 不同的人對於一個程式步伐的定義可能不同, 因此不同的人對同一個程式計算出來的程式步伐都不會相同. 這個就好像空間複雜度那樣, 我們可以以位元組為基本單位, 但是也可以以變數為基本單位. 為了統一起見, 即使一個表達式中存在多個運算元, 那麼也只算作一個步伐. 另外, 所有內建型別的操作都視為一個步伐.

只要我們統一標準, 任意程式碼的時間步伐都可以讓程式自動進行計算. 考慮程式碼

int sum(const int arr[], int n) {
    auto sum {0};
    for(auto i {0}; i < n; ++i) {
        sum += arr[i];
    }
    return sum;
}

我們可以主動加入一個用於時間步伐計數的變數, 每走過一個時間步伐都讓這個變數增加一 :

auto step_count {0};

int sum(const int arr[], int n) {
    auto sum {0};
    ++step_count;        // 對變數 sum 的初始化是一個步伐
    ++step_count;       // 看到下面的 for 迴圈中, 對變數 i 的初始化是一個步伐
    for(auto i {0}; i < n; ++i) {
        ++step_count;       // 表達式 i < n 的判定是一個步伐
        sum += arr[i];
        ++step_count;       // 對 sum 的累加是一個步伐. 即時上面改為 sum = sum + arr[i], 那麼仍然算作一個步伐
        ++step_count;       // ++i 是一個步伐
    }
    ++step_count;       // 對於最後一次 i < n 的判定是一個步伐, 但是它不在迴圈內被計入, 因此要額外計入
    ++step_count;       // return 陳述式是一個步伐
    return sum;
}

如果參數 arr 中有 n 個元素, 那麼我們不難得出, 函式 sum 所需要的程式步伐為 3n + 4, 通常我們記為 T_{\mathrm {sum}}(n) = 3n + 4. 其中, n 是實體特徵. 這裡注意區別 T(n) 和上面提到的 t_{P}(n), T(n) 是時間步伐函數, t_{P}(n) 是程式的運作時間. 不過, 對於每一個程式碼片段, 都這樣去得到程式步伐顯然是不現實的, 為此我們可以建立表格進行分析.

一條陳述式可能只有一個步伐, 但是這條陳述式可能被運作很多次. 例如 Code 3-2 中, for 迴圈中的 sum += arr[i];, 這個陳述式的時間步伐只有 1, 但是它會被運作 n 次. 因此在建立表格進行分析的時候, 我們還需要得到某個陳述式可能會運作多少次, 即陳述式的運作頻率. 某個陳述式真正的步伐是單次運作所需要的步伐乘以它的運作頻率. 除了頻率之外, 我們還需要一個概念, 就是運作步伐, 它也可以被簡稱為步伐. 所謂運作步伐, 就是一個陳述式的步伐之和. 例如 for(auto i {0}; i < 1;) 這樣的陳述式, 在 for 迴圈初始化的時候, 會宣告變數 i, 這裡有一個步伐; 初始化完成之後, 會運作比較判斷式 i < 1, 這裡又是一個步伐. 因此, 這個 for 迴圈的運作步伐應該是 2. 這樣, 一個陳述式的步伐就是運作步伐乘以其頻率. 於是, 我們可以對 Code 3-1 中的函式 sum 建立表格計算總步伐 :

這裡要解釋一下 for 迴圈的頻率為 n + 1 而不是 n 的原因是 i 要初始化, 並且在結束之前 i < n 還要進行多一次的運算. 另外, 總步伐為 2n + 2 + 1 而不是 2n + 2 的原因就在於變數 i 需要初始化, 這個程式步伐不能寫在前面兩個表格中.

有些函式的精確步伐是無法計算的, 例如順序搜尋 :

int search(const int arr[], int n, int x) {
    for(auto i {0}; i < n; ++i) {
        if(arr[i] == x) {
            return i;
        }
    }
    return -1;
}

最好的情況下, 我們在搜尋集合的第一個就找到了要搜尋的元素; 最壞的情況下, 我們在集合地最後一個才找到要搜尋的元素, 甚至要搜尋的元素根本就不在這個集合中. 這個時候, 我們沒有辦法精確地寫出一些陳述式的頻率. 此時, 我們會建立多個表格, 至少要列出最好的情況, 最壞的情況和一般情況. 對於 Code 4, 我們首先計算最好情況下的總步伐 :

然後計算最壞情況下的程式步伐 :

最後計算一般情況下的程式步伐 :

現在我們來計算平均步伐. 平均步伐的計算涉及實體特徵 n 的所有取值. 當函式 search 在陣列第一個元素就找到要搜尋的元素的時候是一種情況; 當函式 serach 在陣列第二個元素就找到要搜尋的元素的時候是第二種情況; ...; 當函式 search 在陣列的第 n 個元素才找到要搜尋的元素的時候是第 n 種情況; 當函式 search 無法在陣列中找到要搜尋的元素是最壞的情況. 平均步伐應該是所有情況的步伐之和取平均數. 對於函式 search 來說, 應該是 \displaystyle {\begin {aligned} T_{\mathrm {search}}(n) &= \frac {1}{n + 1} \left ( 4 + \sum \limits_{i = 2}^{n}3i + 3 + 3n + 3 \right ) \\ &= \frac {1}{n + 1} \left ( \frac {3}{2}n^{2} + \frac {15}{2}n + 1 \right ). \end {aligned}} 現在假設搜尋成功的概率為 \frac {4}{5}, 並且每個元素被搜尋的機率都是相同的, 那麼此時我們可以將平均步伐寫為 \displaystyle {\begin {aligned} T_{\mathrm {search}}(n) &= \frac {4}{5} \cdot \frac {1}{n} \left ( 4 + \sum \limits_{i = 2}^{n}3i + 3 \right ) + \left ( 1 - \frac {4}{5} \right )(3n + 3) \\ &= \frac {9}{5}n + \frac {21}{5} - \frac {8}{5n}. \end {aligned}}

4. 程式碼的實驗分析

第 2 節和第 3 節介紹了如何從理論上對程式碼的空間複雜度和時間複雜度進行分析. 但是一般來說, 對於大型程式或者非常複雜的程式碼, 我們很難從理論上進行計算. 這個時候, 我們通常採用實驗分析的方法對程式碼的空間複雜度和時間複雜度進行分析.

要從實驗的角度分析程式碼的空間複雜度很簡單, 作業系統也提供了很多工具來顯示我們的程式所佔用的記憶體空間和硬碟空間. 例如 macOS 中, Finder 可以顯示程式的資料, 包括佔用了多少硬碟空間, 什麼時候創建的; 在程式運作的時候, 活動監視器也可以顯示程式佔用了多少記憶體.

要從實驗的角度分析程式碼的時間複雜度會稍複雜. 當然, 我們可以用秒錶計算程式的響應時間, 但是這個顯然是不准的, 因為人的反應是秒級的, 而電腦運作程式是毫秒級甚至微秒級的. 在 C++ 中, 我們可以借助來自標頭檔 <ctime> 中的函式 std::clock 來比較精確地計算程式碼片段的運作時間 :

#include <ctime>

int main(int argc, char *argv[]) {
    auto start {std::clock()};
    // 要統計運作時間的程式碼片段
    // ...
    auto end {std::clock()};
    auto time {static_cast<double>(end - start) / CLOCKS_PER_SEC};      // 運作時間, 精確到秒
}