[Algorithm] 複雜度分析

漸進符號

當輸入規模 $n$ 夠大時，函數的低階項與常數係數對成長趨勢的影響可忽略，只有最高階項決定整體行為。

以 $T(n) = 3n^2 + 100n + 5000$ 為例，$n = 10000$ 時：

• $3n^2 = 3 \times 10^8$
• $100n = 10^6$（僅佔 $n^2$ 項的 0.3%）
• $5000$（可忽略）

因此 $T(n) = O(n^2)$，$n^2$ 項完全主導增長。

化簡規則：

1. 捨棄常數係數：$O(5n) = O(n)$
2. 捨棄低階項：$O(n^2 + n) = O(n^2)$
3. 不同輸入各自獨立：$O(n + m)$ 不能化簡成 $O(n)$，因為 $m$ 可能比 $n$ 大

O、Ω、Θ 的差異

• $O$（Big-O）：上界，演算法不會比這更慢
• $\Omega$（Big-Omega）：下界，演算法不會比這更快
• $\Theta$（Big-Theta）：緊界，上界與下界同階

$\Theta$ 成立的條件：存在 $n_0$ 和正常數 $c, c'$，使得對所有 $n \geq n_0$：

$c' \cdot g(n) \leq f(n) \leq c \cdot g(n)$

以線性搜尋為例：

• Worst case = $O(n)$：目標在最後一個位置，要掃完整個陣列
• Best case = $\Omega(1)$：目標在第一個位置，看一次就找到了
• Average case = $\Theta(n)$：期望上要跑一半，仍然是線性成長

常見複雜度等級

常數時間 O(1)

執行時間與輸入規模無關。典型範例：陣列 index 存取、hash table 無碰撞時的查找。

對數時間 O(log n)

每步將問題規模砍半（或更大比例）。典型範例：二分搜尋——從 $n$ 個元素開始，每次排除一半，共 $\log_2 n$ 次。對數成長極緩慢：$n$ 從 100 萬增至 10 億，$\log_2 n$ 僅從 20 增到 30。

線性時間 O(n)

與輸入規模成正比，需遍歷每個元素至少一次。典型範例：線性搜尋、找最大值、計算陣列總和。許多問題的天然下界就是 $\Omega(n)$（至少要讀過每個輸入一次）。

線性對數時間 O(n log n)

常見於「對每個元素做 $\log n$ 代價的事」或「分而治之、每層合併需要線性代價」的結構。Merge Sort、Heap Sort 屬此等級。比較排序（comparison sort）的理論下界為 $\Omega(n \log n)$——任何只靠比較來排序的演算法，最壞情況不可能更快。

多項式時間 O(nᵏ)

$n$ 的某個固定次方。最常見的是 $O(n^2)$ 和 $O(n^3)$。

$O(n^2)$ 通常來自兩層巢狀迴圈，對每個元素都要跑一遍所有其他元素——Bubble Sort、Insertion Sort、Selection Sort 都是。$n = 1000$ 時大約 $10^6$ 次操作，還可以接受；$n = 10^5$ 時就是 $10^{10}$ 次，在現代硬體上大概要幾十秒，很慢了。

$O(n^3)$ 常見於三層巢狀迴圈，標準的矩陣乘法就是 $O(n^3)$：兩個 $n \times n$ 的矩陣相乘，每個輸出元素要做 $n$ 次乘加，共 $n^2$ 個輸出元素。$n = 1000$ 的矩陣乘法需要 $10^9$ 次操作，需要幾秒鐘。

只要 $k$ 是固定常數，多項式時間演算法在理論上都被認為是「可接受的」——這也是 P 類問題的定義（詳見最後一節）。

指數時間 O(2ⁿ)

通常來自列舉所有子集合（$n$ 個元素的集合有 $2^n$ 個子集）。暴力解背包問題、子集合加總問題屬此等級。$n = 30$ 時已達 $10^9$ 次，$n = 50$ 完全不可行。

階乘時間 O(n!)

列舉所有排列的代價（$n$ 個元素有 $n!$ 種排列）。暴力解旅行推銷員問題即為此等級。$n = 12$ 時約 $4.8 \times 10^8$；$n = 15$ 已超過 $10^{12}$。

例題：用算式推導迴圈複雜度

直覺「兩層迴圈就是 $O(n^2)$」常常對，但考試要的是算式。內層迴圈的次數會隨外層變化時，必須用 Σ 展開、套求和公式，才算完整推導。

(a) 成長率排序

把下列 8 個複雜度由慢到快排序：

$O(n^7),\ O(n^2),\ O(\log \log n),\ O(\log n),\ O(n),\ O(n!),\ O(2^n),\ O(1)$

只要握住三大群組 常數 / 對數 / 多項式 / 指數 / 階乘，再比群內：

$O(1) \subset O(\log \log n) \subset O(\log n) \subset O(n) \subset O(n^2) \subset O(n^7) \subset O(2^n) \subset O(n!)$

• $\log \log n$ 比 $\log n$ 更慢（對 $\log n$ 再取一次對數）
• 多項式之間比次方：$n < n^2 < n^7$
• 指數勝過所有多項式：對任意固定 $k$，$n^k / 2^n \to 0$
• 階乘又勝過指數：$2^n / n! \to 0$（由 Stirling 近似 $n! \sim \sqrt{2\pi n}(n/e)^n$ 可知）

(b) 巢狀迴圈的算式推導

下列片段其實是選擇排序的 1-indexed 寫法：

for i := 1 to n-1 do
{
    j := i;
    for k := i+1 to n do
        if (a[k] < a[j]) then j := k;
    swap(a[i], a[j]);
}

以比較次數（內層 if 的執行次數）作為代價單位，逐層拆解：

• 外層 $i$：從 $1$ 到 $n-1$，共 $n - 1$ 輪
• 內層 $k$：對每個固定的 $i$，$k$ 從 $i + 1$ 掃到 $n$，共 $n - i$ 次比較
• 外層每輪末尾的 $j := i$ 與 swap 都是 $O(1)$，合計 $O(n)$，不影響最高階

總比較次數：

$T(n) = \sum_{i = 1}^{n - 1} (n - i)$

做變數代換 $\ell = n - i$（當 $i = 1$ 時 $\ell = n - 1$，當 $i = n - 1$ 時 $\ell = 1$）：

$T(n) = \sum_{\ell = 1}^{n - 1} \ell = 1 + 2 + \cdots + (n - 1) = \frac{(n - 1)\, n}{2}$

展開並加上外層 $O(n)$：

$T(n) = \frac{n^2 - n}{2} + O(n) = \frac{1}{2} n^2 - \frac{1}{2} n + O(n)$

取最高階項、捨棄常數係數：

$T(n) = O(n^2)$

最壞、最佳、平均情況

同一演算法面對不同輸入，執行時間可能差距很大：

• Worst case：輸入對演算法最不利的情況。這是 $O$ 最常對應的場景。
• Best case：輸入對演算法最有利的情況。這是 $\Omega$ 最常對應的場景。
• Average case：對所有可能輸入取平均（需要假設輸入分佈）。

Quick Sort 是最具代表性的例子：選一個 pivot 將陣列分成兩部分，遞迴排序。

• Best / Average case：$O(n \log n)$：每次 pivot 大概把陣列切成一半，遞迴深度是 $\log n$，每層合計掃 $n$ 個元素，共 $n \log n$。
• Worst case：$O(n^2)$：每次 pivot 都選到最大或最小值，陣列被切成 1 和 n-1，退化成一層一層剝，遞迴深度變 $n$，共 $n^2$。這在已排序的輸入上很容易發生（取決於 pivot 選法）。

主定理（Master Theorem）

分治法將問題拆成若干較小子問題，遞迴解決後合併結果。這類演算法的時間複雜度通常為：

$T(n) = aT\!\left(\frac{n}{b}\right) + f(n), \quad a \geq 1,\; b > 1$

• $a$：每次遞迴拆成幾個子問題
• $b$：每個子問題的規模縮小比例（變成 $n/b$）
• $f(n)$：每次遞迴的合併/拆分代價

主定理提供直接判定 $T(n)$ 成長速度的方法。

關鍵值 $c = \log_b a$

$n^c$ 可以想成遞迴樹總共有多少個葉節點的代價。比較 $f(n)$（合併代價）與 $n^c$（遞迴天然代價），誰大誰主導。

套用流程（四步）

1. 識別 $a$、$b$、$f(n)$
2. 計算 $c = \log_b a$
3. 比較 $f(n)$ 與 $n^c$：誰成長快？
4. 根據結果對應到 Case 1 / 2 / 3，寫出答案

Case 1：遞迴主導 → $T(n) = \Theta(n^c)$

條件：$f(n)$ 比 $n^c$ 慢一個多項式因子，即 $f(n) = O(n^{c - \varepsilon})$，某個 $\varepsilon > 0$。

手把手：$T(n) = 8T(n/2) + O(n^2)$

Case 2：勢均力敵 → $T(n) = \Theta(n^c \log n)$

條件：$f(n) = \Theta(n^c)$，兩邊同階。每層遞迴都貢獻類似代價，共 $\log n$ 層，所以多一個 $\log$。

手把手（Merge Sort）：$T(n) = 2T(n/2) + O(n)$

Case 3：合併主導 → $T(n) = \Theta(f(n))$

條件：$f(n)$ 比 $n^c$ 快一個多項式因子，即 $f(n) = \Omega(n^{c + \varepsilon})$，另需滿足正則條件（實務上大多成立，不詳述）。

手把手：$T(n) = T(n/2) + O(n)$

更多範例對照表

例題：用展開法（不用主定理）推導 $T(n) = 3T(n/3) + O(n)$

為什麼要會展開法：主定理是一個「查表規則」，考試如果老師尚未教到、或題目明說「不得使用主定理」，直接寫結果會被扣分。展開法（又稱 iteration method、substitution by unfolding）是把遞迴式一層一層代入，靠 Σ 求和算出精確階數，屬於第一性原理的推導。

設 $T(1) = 1$，且

$T(n) = 3\, T(n/3) + c n$

其中 $c$ 為常數，代表合併步驟的線性代價。

第 1 層代入

$T(n) = 3\, T(n/3) + c n$

第 2 層代入：把 $T(n/3) = 3\, T(n/9) + c (n/3)$ 帶回

$T(n) = 3\left[3\, T(n/9) + c\,\frac{n}{3}\right] + c n = 9\, T(n/9) + c n + c n = 9\, T(n/9) + 2 c n$

第 3 層代入：把 $T(n/9) = 3\, T(n/27) + c (n/9)$ 帶回

$T(n) = 9\left[3\, T(n/27) + c\,\frac{n}{9}\right] + 2 c n = 27\, T(n/27) + c n + 2 c n = 27\, T(n/27) + 3 c n$

觀察規律：展開到第 $k$ 層

$T(n) = 3^{k}\, T\!\left(\frac{n}{3^{k}}\right) + k \cdot c n$

合併項 $k c n$ 是關鍵——每展開一層，都會再添加一整層的 $c n$ 合併代價（因為 $3$ 個子問題每個帶回 $c (n/3)$，加起來剛好又是 $c n$）。

觸底條件：展開到 $T(1)$ 時停下，即 $n / 3^{k} = 1$，解得

$3^{k} = n \quad \Longrightarrow \quad k = \log_{3} n$

代回

$T(n) = 3^{\log_{3} n} \cdot T(1) + c n \log_{3} n = n \cdot 1 + c n \log_{3} n$

$T(n) = n + c n \log_{3} n = \Theta(n \log n)$

最後一步用到 $\log_{3} n = \frac{\log n}{\log 3}$，$\log 3$ 是常數可吸收到大 O 裡。

共 $\log_{3} n$ 層，每層 $c n$，加上葉層 $n \cdot T(1) = n$，總和：

$T(n) = n + c n \log_{3} n = \Theta(n \log n)$

這個結果也和主定理的 Case 2 一致（$a = 3, b = 3, c = \log_{3} 3 = 1$，$f(n) = n = n^{c}$，同階 → $\Theta(n \log n)$），但展開法給出的是推導過程、不是查表。

問題複雜度（簡介）

• P：能在多項式時間 $O(n^k)$ 內解決的問題（排序、Dijkstra、最大流）
• NP：能在多項式時間內驗證一個解是否正確的問題
• NP-complete：NP 中最難的一批——所有 NP 問題都可多項式時間規約到它（TSP、SAT、背包）
• P ⊆ NP，但 P = NP 尚未證明

常見考法