淺談 Asymptotic analysis 漸進分析的三種符號：O、Ω 及 Θ
引言：為什麼需要漸進分析？
在算法設計中，我們經常需要評估算法的效率。雖然可以通過實際運行算法來測量其執行時間，但這種方法既耗時又不能反映算法在各種輸入規模下的表現。這就是我們需要漸進分析（Asymptotic Analysis）的原因。
漸進分析幫助我們理解當輸入規模趨近無窮大時，算法的執行時間如何增長。這種分析方法使用三種主要符號：Big O、Omega (Ω) 和 Theta (Θ)。
Big O 符號：上界分析
定義
Big O 表示算法在最壞情況下的時間上限。它是最常用的複雜度表示法。
數學表示
如果存在正常數 c 和 n0，使得對於所有 n ≥ n0，有 0 ≤ f(n) ≤ cg(n)，則我們說 f(n) = O(g(n))。
實例
如果一個算法的時間複雜度為 3n^2 + 2n + 1，我們可以說它是 O(n^2)。
驗證方法
要證明 g(n) 是 f(n) 的上界，計算 lim(n→∞) f(n)/g(n) = c。如果 c ≥ 0 且有限，則成立。
小技巧
f(n) 的最高次項不應超過 g(n)，否則極限會趨向無窮大。
Omega (Ω) 符號：下界分析
定義
Ω 表示算法在最佳情況下的時間下限。
數學表示
如果存在正常數 c 和 n0，使得對於所有 n ≥ n0，有 0 ≤ cg(n) ≤ f(n)，則我們說 f(n) = Ω(g(n))。
驗證方法
要證明 g(n) 是 f(n) 的下界，計算 lim(n→∞) g(n)/f(n) = c。如果 c ≥ 0 且有限，則成立。
Theta (Θ) 符號：緊密界分析
定義
Θ 表示算法的平均時間複雜度，同時給出了上界和下界。
數學表示
如果存在正常數 c1、c2 和 n0，使得對於所有 n ≥ n0，有 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n)，則我們說 f(n) = Θ(g(n))。
驗證方法
要證明 g(n) 是 f(n) 的緊密界，計算 lim(n→∞) f(n)/g(n) = c。如果 c > 0 且有限，則成立。
結論
Big O 給出最壞情況下的上界，Omega 給出最佳情況下的下界，而 Theta 則提供了一個更精確的界限範圍。在實際應用中，我們通常更關注 Big O，因為它能幫助我們理解算法在面對大規模輸入時的表現。
關鍵要點
- Big O：最壞情況的上界
- Omega (Ω)：最佳情況的下界
- Theta (Θ)：平均情況的緊密界
通過掌握這些概念，能夠更好地設計和優化算法，為不同的問題選擇最合適的解決方案。