演算法執行時間隨輸入規模增長的趨勢分析
大 O 標記法描述演算法的上界，即在最壞情況下執行時間的成長趨勢。若存在正數 c 和 n₀ 使得當 n ≥ n₀ 時 f(n) ≤ c × g(n)，則 f(n) = O(g(n))。
| 複雜度 | 名稱 | 典型演算法 |
|---|---|---|
| O(1) | 常數 | 雜湊表查找、陣列存取 |
| O(log n) | 對數 | 二分搜尋、平衡樹操作 |
| O(n) | 線性 | 線性搜尋、走訪陣列 |
| O(n log n) | 線性對數 | 合併排序、快速排序 |
| O(n²) | 平方 | 氣泡排序、選擇排序 |
| O(n³) | 立方 | 傳統矩陣乘法 |
| O(2ⁿ) | 指數 | 子集生成、暴力遞迴 |
資料量小於 100 時 O(n²) 可接受；資料量 100-10,000 選擇 O(n log n)；資料量大於 1,000,000 必須 O(n) 或更好。