接著, 我們將要進行資料結構系列的理論篇, 資料結構的魅力也正是在於這些理論. 通過複雜度理論和漸進分析, 我們可以計算某一個程式碼的複雜度和運作時間

程式效能是指運作這個程式所需要的時間和記憶體大小. 一般來說, 我們有兩種方法來測量一個程式的效能 :

• 分析法
• 實驗法

在效能分析的時候, 我們使用分析法; 在效能測量的時候, 我們使用實驗法

空間複雜度是指一個程式運作所需要的記憶體大小, 時間複雜度是指一個程式運作所需要的時間

空間複雜度由程式碼、數據和環境堆疊佔用的容量之和所構成. 程式碼所佔用的容量取決於把程式轉化成機器語言的編碼器、在編碼時編碼器的選項和目標作業系統甚至電腦; 數據所佔用的容量是由所有的常數和變數所需的儲存空間, 另外還包括動態物件所需要的儲存空間; 環境堆疊所佔用的容量是指用來保存因為函式呼叫造成暫停時, 保存必要的信息所需要的儲存空間

一個程式所要佔有的容量空間取決於若干因素, 有些因素在編寫程式碼的時候是無法預知的. 另外, 就算是這些因素已經確定了下來, 但是我們也無法精確地分析出一個程式在運作時所需要的容量大小

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

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

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

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

於是, 任意程式 P 所需要的空間可以表示為

c + S_{P}(實體特徵)

想要精確分析程式的空間複雜度, 還要考慮編碼器編碼的時候所產生的臨時變數佔用的容量, 除了遞迴函式之外, 這些容量通常與實體特徵無關而與編碼器直接相關. 因此, 精確地分析程式的空間複雜度通常不太可能, 於是要分析一個程式的空間複雜度, 我們將目標集中於計算 S_{P}. 對於任意給定的問題, 我們首先要確定哪些實體特徵可以用來估算容量空間的需求. 對於實體特徵為 n 的程式, 若程式並不需要動態配置記憶體空間且函式不是遞迴函式, 那麼有

S_{P}(n) = 0

對於程式碼 :

#include <iostream>



using namespace std;



template <typename T, size_t N>

void func(T (&arr)[N]) {

    auto new_arr {new T[N * 2]};

    //...   此處不再需要配置記憶體, 也不存在遞迴

}

上述程式碼所需要的可變空間為 sizeof(T) * n * 2, 由於 n 為實體特徵, 因此對於上述程式碼, 有

S_{P}(n) = sizeof(T) * 2 * N

接下考察遞迴的程式碼 :

int sum(int *arr, int n) {

    if(n > 0) {

        return arr[n - 1] + sum(arr, n - 1);

    }

    return 0;

}

對於遞迴, 首先要考慮的便是遞迴深度問題. 當 n == 0 的時候, 遞迴深度為 0, 此時有

S_{P}(0) = 0

當 n > 0 的時候, 第一次呼叫後進入 if 條件陳述式, 第二次呼叫時需要保留第一次呼叫的 arr 記憶體位址和 n 的數值. 在 64 位元的裝置上, 任意指標的大小為 8 個位元組, 一個 int 變數的大小為 4 個位元組. 除了參數之外, 回傳值也需要保存, 因此也佔用了 4 個位元組. 對於遞迴深度, 是直到 n == 0 的時候才結束, 因此遞迴深度為 n + 1. 因此, 對於上述程式碼, 有

S_{P}(n) = 16 * (n + 1)

一個程式 P 所需要的時間是編碼的時間和運作的時間之和. 編碼時間通常和實體特徵的關係不大, 而一個程式通過一次編碼可以反覆運作多次, 因此編碼時間自然就不是關注的重點, 關注的重點是運作時間. 運作時間通常使用

t_{P}(實體特徵)

來表示. 我們在構思一個程式的時候, 對於可能影響 t_{P} 值的因素還不是很清楚, 因此僅僅能對其值進行估算. 如果我們了解編碼器, 那麼可以通過得到 t_{P} 的運算式. 令 n 表示實體特徵, 則有

t_{P}(n) = C_{ADD} \cdot ADD(n) + C_{SUB} \cdot SUB(n) + C_{MUL} \cdot MUL(n) + C_{DIV} \cdot DIV(n) + C_{CMP} \cdot CMP(n) + C_{LOAD} \cdot LOAD(n) + ...

其中, C_{i} (i \in \left \{ ADD, SUB, MUL, DIV, CMP, LOAD ,... \right \}) 表示對應操作所需要的時間; ADD、SUB、MUL、DIV、CMP 和 LOAD 等分別表示加、減、乘、除、比較和匯入操作針對實體特徵 n 所需要的次數

對於不同的型別, 進行不同操作所需要的時間也不相同, 而且不同裝置處理運算式的方式可能也不盡相同. 因此使用分析法確定一個程式的運作時間非常複雜, 幾乎無法計算精確的運作時間, 只能估算運作時間 :

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

某些函式的操作計數是無法確定的, 比如泡沫排序, 其操作計數不但取決於實體特徵, 還取決於序列的排列. 因此, 平均操作計數不易統計. 一般來說, 我們集中計算出最好情況下的操作計數, 然後集中計算出最壞情況下的操作計數, 最後取平均數來當作平均操作計數

以順序搜尋為例, 如果串列中有 n 個不同的元素, 要搜尋的元素足夠隨機, 以至於串列中所有元素被搜尋的概率都相等, 那麼每個元素的查找所需要進行的比較次數之和為

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

平均每個元素在搜尋時比較的次數為

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

程式的時間複雜度除了和實體特徵有關之外, 還與一些無關於實體特徵的操作有關. 例如對於一個排序演算法, 我們可能需要初始化一些用於迴圈結束判定的輔助變數, 這也需要一定的時間. 在對順序搜尋進行分析的時候, 我們僅僅分析了我們所感興趣的搜尋的那一部分, 而忽略了那些輔助的部分. 我們稱這樣的計數方法為作業計數. 作業計數也是估算程式時間複雜度的一種方法, 但是僅僅是針對我們特定的操作, 而忽略了其餘操作. 由於我們所感興趣的操作都和實體特徵有關, 因此通常作業計數所得到的函數也是實體特徵的函數. 如果我們要針對感興趣的部分和不感興趣的部分, 也就是程式的全部都進行統計, 那麼次數我們稱作為步伐. 由於程式的步伐包含了感興趣的部分, 而這部分通常和實體特徵有關, 因此程式的步伐必定是實體特徵的函數

為了精確地計算出程式的時間複雜度, 我們需要程式步伐的定義

定義 : 一個程式步伐可以大概定義為一個語法上或著語意上的程式片段, 這個片段運作的時間獨立於實體特徵

雖然程式步伐有了大概的定義, 但是程式步伐的精確定義確實因人而不同的. 考慮 C++ 陳述式 :

y = a + b + c;

如果把 x + y 算作一個程式步伐, 則 a + b + c 有兩個程式步伐, 然而把結果指派給 y 還需要一個程式步伐. 那麼上述陳述式有 3 個程式步伐. 除此之外, 我們還可以把上面的陳述式只算作一個程式步伐

我們看到, 不同的人對於一個程式步伐的定義可能不同, 因此不同的人對同一個程式計算出來的程式步伐都不會相同. 為了解決這個問題, 在資料結構系列的文章中, 我們這樣約定程式步伐 : 當某個陳述式的運作時間獨立於實體特徵, 那麼就將其視為一個程式步伐. 那麼陳述式 y = a + b + c; 就只有一個程式步伐

有了這個約定, 我們大致可以得到, 對於內建性別來說 :

• 對於某個變數或著常數的初始化算作一個程式步伐
• 對於某個陳述式, 即時存在多個運算子, 那麼也只算作一步

因此, 如果一個函式沒有用到非 POD 類別, 那麼可以使用一個變數來計算某個函式的程式步伐. 考慮以下程式碼 :

int sum(const int *arr, int n) {

    auto sum {0};

    for(auto i {0}; i < n; ++i) {

        sum += arr[i];

    }

    return sum;

}

要計算上述程式碼的程式步伐, 我們首先宣告一個程式步伐標誌變數 step_count. 當程式每進行一個程式步伐, 那麼就讓 step_count 增加一

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;

}

那麼我們不難得出, 函式 sum 所需要的程式步伐為 3n + 4, 其中 n 為實體特徵

令 T(n) 是某一函式呼叫終結時, step\_count 的增加值, 記 step_count 的初始值為 step\_count\_start, 那麼有

T(n) = step\_count - step\_count\_start

對於 sum 函式, 當 n = 0 的時候, T(0) = 4; 當 n > 0 的時候, T(n) = 3n + 4. 綜合可得遞迴方程式 T(n) = T(n - 1) + 3 :

\begin {aligned} T(n) &= T(n - 1) + 3 \\ &= T(n - 2) + 3 + 3 \\ &= T(n - 2) + 6 \\ &=\ ... \\ &= 3(n - 1) + T(1) \\ &= 3(n - 1) + 3 + T(0) \\ &= 3n + 4 \end {aligned}

因此, 程式步伐確實可以幫助我們分析程式的運作時間是如何隨著實體特徵的變化而變化的

除了使用程式步伐計數變數 step_count 之外, 還可以建立一張表, 列出每條陳述式的程式步伐. 為此, 首先要確定每條陳述式每次運作所需要的程式步伐一集該陳述式的運作次數, 即頻率. 然後把這兩個數據相乘便可以得到每條陳述式的總程式步伐. 把所有陳述式的總程式步伐相加, 就可以得到整個程式的程式步伐. 這種方法又被稱為剖析法

剖析法要求我們引入另外一個概念 : 運作步伐. 我們定義運作步伐是一條陳述式運作結束之後, 程式步伐 step_count 的增加值加上這條陳述式本身運作所需要的程式步伐. 比如陳述式

x = sum(arr, sizeof arr / sizeof arr[0]);

將函式 sum 計算得到的結果指派給 x 需要一個程式步伐, 因此上述陳述式的程式步伐是 1, 但是函式 sum 本身還需要計數程式步伐, 因此定義上述陳述式的執行步伐為 1 + T(sizeof arr / sizeof arr[0])

有些人可能會疑惑為什麼 sizeof arr / sizeof arr[0] 並不算作一個程式步伐, 這是因為編碼器具有優化程式碼的能力, 編碼器會將那些能夠放在編碼期就能夠得到的結果儘量都放置在編碼期就計算完成. 如果 sizeof arr / sizeof arr[0] 在編碼期就被計算出來了, 那麼它就不能算作一個程式步伐, 而現代編碼器都有這樣的能力

我們針對函式 sum 建立表格 :

for 迴圈的頻率為 2n + 2 是因為 i 要初始化, 並且在結束之前 i < n 還要進行多一次的運算

最後, 我們再以順序搜尋舉例, 將最好、最壞和平均作業計數的概念擴充到程式步伐中 :

上述表格說明了在最壞的情況下的程式步伐數量, 而最好的情況則是一次就找到, 此時程式步伐為 4 :

為了得到平均程式步伐, 我們不妨假定陣列 arr 中的 n 個元素都不相同, 並且要搜尋的 x 與陣列中任意元素相等的概率都相同. 在這樣的假定下, 一次搜尋成功的平均程式步伐是 n 個搜尋成功的執行步伐的和除以 n, 其中 n 為實體特徵. 我們首先得到 x == arr[i] 時的程式步伐, 其中 i \in [0, n) :

現在可以計算搜尋成功的平均程式步伐了 :

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

現在假設搜尋成功的概率為 \frac {4}{5}, 並且每個 x == arr[i] 被搜尋的機會相同, 此時平均的程式步伐為 :

\begin {aligned} & \frac {4}{5}( 搜尋成功時的平均程式步伐) + (1 - \frac {4}{5})(不成功搜尋時的程式步伐) \\ \\ &= \frac {4}{5} \cdot \frac {3(n + 1)}{2} + \frac {1}{5} \cdot (3n + 3) \\ \\ &= \frac {8n + 9}{5} \end {aligned}