演算法分析與複雜度類別

演算法分析用於建立演算法的資源需求如何隨輸入增長。在實作細節、硬體與具代表性的工作負載掩蓋主要成本之前，它能支援設計決策。有效的分析需要識別輸入大小、指定資源，並在推導界限之前陳述成本模型。

定義成本 #

選擇能代表輸入的大小參數。陣列演算法通常使用 \(n\)，而圖形演算法則需要同時考慮頂點 \(V\) 與邊 \(E\)。也要指定資源，例如比較次數、記憶體使用量、磁碟 I/O、網路往返次數，或在已定義機器模型下的經過時間。

RAM 模型將對字組大小值執行的算術、比較、索引與指標操作視為常數時間操作。這項假設使該模型適用於記憶體內演算法；而外部記憶體演算法必須計算區塊傳輸次數，因為隨機磁碟存取並不具有固定成本。

漸近記號 #

漸近記號比較輸入增長時的非負成本函數。常數因子與低階項不會改變增長類別，因此會予以省略。

當存在常數 \(c > 0\) 與 \(n_0\)，使得對每個 \(n \geq n_0\) 都有 \(f(n) \leq c g(n)\) 時，\(f(n) \in O(g(n))\)。Big O 提供漸近上界。
當 \(g(n) \in O(f(n))\) 時，\(f(n) \in \Omega(g(n))\)。Big Omega 提供漸近下界。
當上述兩個關係都成立時，\(f(n) \in \Theta(g(n))\)。Big Theta 提供漸近緊確界。

例如，\(3n^2 + 10n + 4\) 屬於 \(\Theta(n^2)\)。在已排序陣列中，二分搜尋會進行 \(O(\log n)\) 次比較；而使用鄰接串列表示的圖進行廣度優先搜尋需要 \(\Theta(V + E)\) 時間。未標明所測量資源的界限可能造成誤導：比較排序可以使用 \(O(n \log n)\) 次比較，但仍可能需要 \(O(n)\) 的輔助記憶體。

分析反覆運算演算法 #

計算每個迴圈執行的工作量，並將所有反覆運算的工作量加總。連續迴圈的成本相加；只有在其中一個迴圈的每次反覆運算都會執行另一個迴圈的全部反覆運算時，巢狀迴圈的成本才會相乘。

cpp

#include <cstddef>
#include <vector>

std::size_t lower_bound_index(const std::vector<int>& values, int target) {
    std::size_t first = 0;
    std::size_t last = values.size();

    while (first < last) {
        const std::size_t middle = first + (last - first) / 2;
        if (values[middle] < target) {
            first = middle + 1;
        } else {
            last = middle;
        }
    }
    return first;
}

每次反覆運算都會使搜尋區間至少減半。因此，其執行時間為 \(O(\log n)\)，而反覆運算實作使用 \(O(1)\) 的輔助空間。依賴先前迴圈變數的迴圈界限需要使用總和進行分析；例如，\(\sum_{i=1}^{n} i = \Theta(n^2)\)。

遞迴關係與分治 #

遞迴演算法通常會產生遞迴關係。合併排序將輸入分成兩半，並執行線性合併，因此得到：

\[ T(n) = 2T(n / 2) + \Theta(n) \]

遞迴具有 \(\log_2 n\) 個層級，而每個層級執行 \(\Theta(n)\) 的工作。因此，合併排序的執行時間為 \(\Theta(n \log n)\)。遞迴樹可以直接呈現這種結構。對於形如 \(T(n) = aT(n / b) + f(n)\) 的遞迴關係，主定理會藉由比較 \(f(n)\) 與 \(n^{\log_b a}\) 來分類結果；當其前提條件不適用時，請使用遞迴樹或代入法證明。

最壞情況、期望成本與攤銷成本 #

最壞情況分析會界定給定大小的每個輸入。即使最壞輸入很少出現，它仍可提供可靠的容量上限。平均情況分析需要明確的輸入分布；如果沒有這樣的分布，稱某個界限為「平均」並沒有數學意義。

期望分析涵蓋隨機化演算法。當樞紐選擇避免對抗性順序時，隨機化快速排序的期望執行時間為 \(\Theta(n \log n)\)，儘管某次特定執行可能需要 \(\Theta(n^2)\) 時間。

攤銷分析不假設輸入分布，而是界定一系列操作。向以幾何方式成長的 std::vector 追加元素時，偶爾會重新配置並複製 \(\Theta(n)\) 個元素，但每個元素只會被複製有限次。因此，一系列追加操作的總成本相當於每次追加 \(O(1)\) 的攤銷時間。聚合法、記帳法與位能法是證明這類界限的等價方法。

決策問題與 NP 完全性 #

決策問題的答案是 yes 或 no。複雜度類別定義在決策問題上，因為多項式時間歸約會保留這些答案。

當決定性機器能在多項式時間內判定某個語言時，該語言屬於 P。當每個 yes 實例都具有可由決定性機器在多項式時間內驗證的憑證時，該語言屬於 NP。因此，\(P \subseteq NP\)。

如果 NP 中的每個問題都能在多項式時間內歸約到某個問題，該問題就是 NP 困難。如果一個問題同時是 NP 困難且屬於 NP，它就是 NP 完全。NP 完全性證明需要：

用於證明屬於 NP 的多項式時間驗證器；以及
從已知 NP 完全問題進行的多項式時間歸約。

\(P = NP\) 是否成立仍然是未解決問題。NP 完全性不代表實際實例無法求解；問題結構、參數界限、近似演算法與啟發式方法都可能使特定實例變得可處理。