第十四章：求和與漸近 — 動畫敘事
第十四集 · Ch.14 求和與漸近
大 O 記號
「這個演算法跑多快？」
精確的答案往往複雜又難比較。
大 O 記號讓我們只關注最重要的部分——
當 n 趨近無窮大時，哪一項主導？
精確的答案往往複雜又難比較。
大 O 記號讓我們只關注最重要的部分——
當 n 趨近無窮大時，哪一項主導？
漸近記號三兄弟
O
大 O（上界）
f(n) = O(g(n))
f 最多和 g 一樣快
例：3n²+5n = O(n²)
f 最多和 g 一樣快
例：3n²+5n = O(n²)
Ω
大 Ω（下界）
f(n) = Ω(g(n))
f 至少和 g 一樣快
例：n²+1 = Ω(n)
f 至少和 g 一樣快
例：n²+1 = Ω(n)
Θ
大 Θ（緊界）
f(n) = Θ(g(n))
f 和 g 同階
例：2n²+3n = Θ(n²)
f 和 g 同階
例：2n²+3n = Θ(n²)
常見複雜度排序
n = 1000 時的運算次數（對數座標）
越左邊越快，越右邊越慢
幾何級數求和
幾何級數公式
1 + r + r² + … + rⁿ = (rⁿ⁺¹ - 1) / (r - 1)當 |r| < 1 時（無窮級數）：
1/(1-r)應用：
• 二進位：
1+2+4+…+2ⁿ = 2ⁿ⁺¹ - 1• 電腦演算法：分治法的複雜度分析
• 金融：等比年金計算
互動：複雜度比較器
10
觀念測驗
下列哪個說法正確？
小結
複雜度
決定可行性
決定可行性
O(n log n) 的排序和 O(n²) 的排序，
在 n = 10⁶ 時差了 50 萬倍。
大 O 記號讓我們在設計演算法時，
就能預見這個差距。
在 n = 10⁶ 時差了 50 萬倍。
大 O 記號讓我們在設計演算法時，
就能預見這個差距。
下一集：基數規則——組合計數的基礎
閱讀完整第十四章互動教材 →
1 / 7
本頁為動畫敘事版。看完後可前往 完整第十四章 進行互動練習。
教材來源：Mathematics for Computer Science (Lehman, Leighton, Meyer)