Part III: Counting
第十四章：求和與漸近
在演算法分析中，我們經常需要計算運算的總次數（求和），並比較不同演算法在輸入規模變大時的表現（漸近分析）。
14.1 求和
求和公式是分析迴圈複雜度的基礎。常見的公式包括：
- 算術級數： $\sum_{i=1}^n i = \frac{n(n+1)}{2}$
- 平方和： $\sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6}$
- 幾何級數： $\sum_{i=0}^n x^i = \frac{x^{n+1}-1}{x-1}$ (for $x \neq 1$)
🧪 互動：求和可視化
調整滑桿來改變 $n$ 的值，觀察求和結果如何變化。
$\sum_{i=1}^{3} i^2 = $ 14
公式計算： $\frac{n(n+1)(2n+1)}{6} = \frac{3(4)(7)}{6} = 14$
左圖將平方和視為一層層堆疊的方塊。公式則提供了快速計算總數的方法。
14.7 漸近符號
漸近符號用於描述函數在極限情況下的增長行為，忽略常數和低階項。
大 O 符號 (Big-O)：
$f(x) = O(g(x))$ 表示 $f(x)$ 的增長速率最終不會超過 $g(x)$。
正式定義：存在常數 $c > 0$ 和 $x_0$，使得對於所有 $x \ge x_0$，都有 $|f(x)| \le c \cdot g(x)$。
$f(x) = O(g(x))$ 表示 $f(x)$ 的增長速率最終不會超過 $g(x)$。
正式定義：存在常數 $c > 0$ 和 $x_0$，使得對於所有 $x \ge x_0$，都有 $|f(x)| \le c \cdot g(x)$。
其他符號還有 $\Omega$ (下界) 和 $\Theta$ (精確界)。
🎮 挑戰：函數增長率排序
將下方的函數按照增長速率由慢到快（由小到大）進行排序。
教材來源：Mathematics for Computer Science (Lehman, Leighton, Meyer)