最後更新：2026-06-23

Big-O 成長率

Big-O 記法對演算法的資源需求隨資料規模變化的方式進行分類。它不量測特定機器上的執行秒數，而是捕捉成長的形態——當 n 加倍時，工作量是否也加倍，還是變為四倍？以下六種複雜度是教科書和技術面試中最常見的類別。

六種常見複雜度級別

O(log n) — 對數級。 每個步驟消除剩餘工作量中的固定比例。對包含十億個元素的已排序陣列進行二分搜尋，只需 30 次比較，因為每次都將搜尋空間縮減一半。平衡二元搜尋樹的查詢和許多分治遞迴均屬此類。

O(n) — 線性級。 工作量與資料規模成正比增長。掃描陣列一次找到最大值、計算字串中的字元數或讀取清單中的每個元素，均為線性複雜度，通常被認為是高效的演算法。

O(n log n) — 線性對數級。 排序演算法最常見的複雜度。合併排序、堆積排序和 Timsort（Python 和 Java 使用）均達到 O(n log n)，這也是基於比較的排序演算法的理論下界。在 $n = 10^6$ 時，約需兩千萬次運算，實際表現很快。

O(n²) — 二次方級。 對資料進行兩層巢狀迴圈。氣泡排序、插入排序和樸素矩陣乘法的最壞情況均為 O(n²)。在 $n = 10^4$ 時需一億次運算；在 $n = 10^6$ 時變為一兆次——對大型資料不可行。

O(2ⁿ) — 指數級。 每增加一個元素，工作量加倍。樸素遞迴費波那契演算法重複計算子問題；暴力枚舉所有子集的演算法也以 $2^n$ 的速度成長。當 n = 40 時，次數已超過一兆。

O(n!) — 階乘級。 日常演算法分析中成長最快的類別。對排列問題的暴力求解——如枚舉旅行推銷員問題中所有可能的路線——每個排列對應一次運算，而排列共有 $n!$ 個。當 n 等於二十時，次數超過兩百京（$2 \times 10^{18}$）。

n = 20 時的計算範例

$\log_2 20 \approx 4.32 \quad\quad 20 \quad\quad 20 \log_2 20 \approx 86.4$

$20^2 = 400 \quad\quad 2^{20} = 1{,}048{,}576 \quad\quad 20! \approx 2.43 \times 10^{18}$

n = 20 時，O(n log n) 與 O(n!) 之間的比值約為 $10^{16}$——相當於快速排序與等待時間超過宇宙年齡之間的差距。

實際應用建議

在資料規模較小時，常數因子和快取效果比複雜度更重要；規模增大後，複雜度則主導效能。n = 10,000 大約是 O(n²) 在現代硬體上開始令人不適的門檻（假設為簡單運算）。超過 $10^6$ 後，通常需要 O(n log n) 或更好的演算法。指數級和階乘級演算法對任何實際輸入都需要近似法、動態規劃或剪枝策略。

如需處理資料規模的二進位或十六進位表示，請參閱 進制轉換工具。