核心概念#
本附錄介紹計算複雜度的基本概念，這是衡量算法好壞的客觀標準。優秀的程式員總是不斷尋找更好的算法，而在所有「好」算法中存在一個最優的算法——找到它是計算機科學家努力的目標。
大 O 記號與複雜度衡量#
- 計算量是問題規模 $N$ 的函數 $f(N)$，用大 $O$ 記號表示其上界（或下界）
- 若 $f(N) = N \cdot \log N$ 且 $g(N) = 100 \cdot N \cdot \log N$，兩者在大 $O$ 概念下相同，屬於同一數量級
- 複雜度關鍵看 $O$ 括號裡的函數部分，而非常數因子。例如 $10000 \cdot N \cdot \log(N)$ 當 $N$ 足夠大時遠小於 $0.00001 \cdot N^2$
常見算法的複雜度#
| 問題/算法 | 複雜度 | 說明 |
|---|---|---|
| 哈希查找 | $O(1)$ | 常數複雜度 |
| 有序數組二分查找 | $O(\log N)$ | 對數複雜度 |
| 無序數組任意元素查找 | $O(N)$ | 線性複雜度 |
| 圖遍歷算法 | $O(N)$ | 節點數 $N$ 的線性複雜度 |
| 快速排序算法 | $O(N \log N)$ | |
| 動態規劃/最短路徑 | $O(d^2 \cdot N)$ | 深度 $d$ 的平方複雜度，長度 $N$ 的線性複雜度 |
| 鮑姆-韋爾奇算法 | $O(d^2 \cdot N)$ | 同上 |
| 貝葉斯網路訓練算法 | NP 完全 | 尚未找到多項式複雜度算法 |
P 問題與 NP 問題#
- P 問題（Polynomial）：計算量不超過 $N$ 的多項式函數，被認為計算機可以「有效」解決
- NP 問題（Nondeterministic Polynomial）：能在多項式時間內驗證一個答案的正確與否，但不一定能在多項式時間內找到答案
- NPC 問題（NP-Complete）：1970 年代初，庫克（Stephen Cook）和李文（Leonid Levin）發現所有 NP 問題都可以在多項式時間內歸約到 NPC 問題。若任何一個 NPC 問題找到多項式算法，則 NP=P
- NP-Hard 問題：計算複雜度至少是 NP 完全甚至更大的問題
P 是否等於 NP 是計算機科學中最重要的未解問題之一。目前多數學者相信 P ≠ NP，但尚無定論。
本附錄小結#
數學在計算機科學中的一個重要作用，就是找到計算複雜度盡可能低的解。對於那些至今找不到多項式算法而又無法迴避的問題（如貝葉斯網路訓練），我們只好簡化問題找近似解。