演演算法的複雜度分析

簡介

複雜度分析法是對已知的程式碼進行效率分析的方法，與之相對的是使用實際資料執行程式碼的事後統計法。

複雜度分析法和事後統計法各有優劣，與複雜度分析法進行比較，事後統計法會有以下侷限性：

• 測試結果非常依賴測試環境。硬體的不同會對測試結果有比較大的影響，比如不同處理器的執行時間會不一樣
• 測試結果受資料的影響很大。對同一個排序演演算法，待排序資料的有序度會影響演演算法的執行時間；對於小規模的資料排序，插入排序的效率會比快速排序的效率更高

相比事後統計法，複雜度分析法更能表示一個演演算法在各個維度的綜合效能。

複雜度

複雜度分為時間複雜度和空間複雜度，但是它們並不能準確地表示演演算法的執行時間和儲存空間。

時間複雜度表示的是執行時間與資料規模之間的增長關係；空間複雜度表示的是儲存空間與資料規模之間的增長關係。

複雜度表示法

常用的複雜度表示法就是大 O 複雜度表示法，時間複雜度和空間複雜度都能運用這個概念，在概念上可以進行類比。

在實際使用中，空間複雜度會比時間複雜度更簡單些，下面只對時間複雜度做解析。

大 O 時間複雜度表示法

int cal(int n) {
    int sum = 0;
    int i = 1;
    for (; i <= n; ++i) {
        sum = sum + i;
    }
    return sum;
}

對上述程式碼著手，解析這段程式碼的時間複雜度。

第 2 行和第 3 行僅會執行一次，但第 4、5、6 行是一個 for 迴圈，將會執行 n 次，因此，整個函數執行的次數可以簡單地認為是 n + 2 次。

假如將一行程式碼的執行時間算作單位時間，以此做類比，則此函數的執行時間 \(T(n)\) 與程式碼的執行次數 n 成正比：

其中，n 表示資料規模的大小；\(f(n)\) 表示每行程式碼執行的次數總和，因為這是一個公式，所以用 \(f(n)\) 來表示；\(T(n)\) 表示程式碼執行的時間。公式中的 O 表示程式碼的執行時間 \(T(n)\) 與 \(f(n)\) 表示式成正比。

大 O 時間複雜度實際上並不具體表示程式碼真正的執行時間，而是表示程式碼執行時間隨資料規模增長的變化趨勢。

所以，大 O 時間複雜度也叫作漸進時間複雜度（asymptotic time complexity），簡稱時間複雜度。

從定義上理解，大 O 符號是一種演演算法「複雜度」的「相對」「表示」方式：

• 複雜度：表示相對其他東西的度量結果
• 相對：只能比較相同的事物，不能將一個做算數乘法的演演算法和排序整數列表的演演算法進行比較
• 表示：大 O 符號把演演算法間的比較簡化為一個單一變數

時間複雜度分析

變數法則

程式碼中的變數決定時間複雜度。

大 O 複雜度表示法是一種函數的表示方式，函數中存在至少一個變數，這其實就說明了大 O 複雜度表示法展示了程式碼執行時間隨資料規模增長的變化趨勢。

所以，在分析時間複雜度的時候，需要記住程式碼中的變數決定時間複雜度，觀察程式碼中具體哪一個資料變數在實際執行中最能體現執行時間的趨勢。

加法法則

總複雜度等於量級最大的那段程式碼的複雜度。

大 O 複雜度表示法只是表示一種變化趨勢，一般認為，與公式中的高階 n 值相比，常數、係數、低階量級與演演算法的增長趨勢關係不大。

為了降低複雜性以及提高對比性，通常會忽略掉公式中的常數、係數、低階，只記錄其中最大階的量級即可。

因此，在分析一個演演算法、一段程式碼的時間複雜度時，一般只需關注迴圈執行次數最多的那一段程式碼即可。

通常，核心程式碼執行次數的 n 的量級，就是整段要分析程式碼的時間複雜度。

乘法法則

巢狀程式碼的複雜度等於巢狀內外程式碼複雜度的乘積。

在實際開發中，巢狀迴圈的程式碼比較常見，這裡涉及到巢狀迴圈的時間複雜度分析。

如果把一次迴圈看作是 n 次，每次迴圈當中又會再做一次內迴圈，再把這次內迴圈看作是 m 次，這樣整體迴圈就可以看作是 \(n \times m\) 次，這就是乘法法則。

大部分演演算法複雜度分析中，會經常遇到如 \(n^2\)、\(n^3\) 這樣的時間複雜度，也使用到乘法法則。

常見時間複雜度

常見的時間複雜度有很多，如 \(O(1)\)、\(O(\log n)\)、\(O(n)\)、 \(O(n \log n)\)、\(O(n^2)\)、\(O(n^3)\)、\(O(n^k)\)、\(O(2^n)\)、\(O(n!)\) 等。

時間複雜度可以分為多項式量級和非多項式量級兩種，多項式量級指的是以 n 作為底數，非多項式量級指的是不以 n 作為底數的非確定量級。

當資料規模 n 越來越大時，非多項式量級演演算法的執行時間會急劇增加，求解問題的執行時間會無限增長。

因此，非多項式時間複雜度的演演算法是非常低效的演演算法，實際編碼中需要儘量避免這種情況出現。

常見的時間複雜度中，非多項式量級只有 \(O(2^n)\)、\(O(n!)\) 兩個，其他的都是多項式量級。

其實，時間複雜度超過 \(O(n \log n)\) 的演演算法就可以稱為指數級增長的演演算法，應儘量避免。

常數級

\(O(1)\) 是常數級時間複雜度的一種表示方式，只要程式碼的執行時間不隨 n 的增大而增長，這樣程式碼的時間複雜度就被記作 \(O(1)\)。

一般情況下，只要演演算法中不存在迴圈語句、遞迴語句，即使有成千上萬行的程式碼，其時間複雜度也是 \(O(1)\)。

對數級

對數級時間複雜度非常常見，同時也是最難分析的一種時間複雜度。

實際上，不管是以 2 為底、以 3 為底，還是以 10 為底，都可以把所有對數階的時間複雜度都記為 \(O(\log n)\)。

\(O(\log_3n) = O(\log_32) \times O(\log_2n)\) => \(O(\log_3n) = O(C \times \log_2n)\)，其中 \(C = log_32\) 是一個常數可忽略不計。

如果一段程式碼的時間複雜度是 \(O(\log n)\)，然後程式碼迴圈執行 n 遍，這段程式碼就是 \(O(n \log n)\) 的時間複雜度。

\(O(n \log n)\) 也是一種常見的演演算法時間複雜度。比如歸併排序、快速排序的平均時間複雜度都是 \(O(n \log n)\)。

多變數級

顧名思義，多變數級時間複雜度受多個變數影響，表示一個時間複雜度由多個資料的規模來決定。

這種情況不能隨意使用加法法則省略掉其中一個，而是兩個變數都需要使用到，如 \(O(m \times n)\)、\(O(m + n)\) 都是多變數級的複雜度。

時間複雜度維度

最好情況時間複雜度

最好情況時間複雜度就是，在最理想的情況下，執行這段程式碼的時間複雜度。

最壞情況時間複雜度

最壞情況時間複雜度就是，在最糟糕的情況下，執行這段程式碼的時間複雜度。

平均時間複雜度

平均時間複雜度會將所有可能情況下的執行次數和其發生的頻率聚合起來計算加權平均值，這裡涉及到概率論的知識，因此平均時間複雜度又被稱為加權平均時間複雜度、期望時間複雜度。

均攤時間複雜度

均攤時間複雜度是一種適用場景更少的表示方式，對於某些特殊的場景（比如一種場景是大部分情況下時間複雜度都很低，只有個別情況下時間複雜度比較高，而且這些操作之間存在前後連貫的時序關係），可以引入攤還分析法計算得出均攤時間複雜度。

對於上面描述的場景，可以將這一組操作放在一起分析，嘗試將較高時間複雜度那次操作的耗時平攤到其他那些時間複雜度較低的操作上。

均攤時間複雜度是一種特殊的平均時間複雜度。通常，在能夠應用均攤時間複雜度分析的場合，一般均攤時間複雜度就等於最好情況時間複雜度。

複雜度變化趨勢

上圖是常見覆雜度的變化趨勢，可以清晰地看到，超過 \(O(n \log n)\) 的複雜度就可以隨著 n 的變化而急劇變化，在實際開發中，應儘量避免。