01.2-遞迴的BigO複雜度計算

遞迴的 Big O 複雜度計算 是分析遞迴演算法運行時間的重要方法，主要透過建立遞迴關係式，並進一步求解來獲得時間複雜度。以下是具體內容講解：

1. 遞迴演算法的複雜度分析基礎#

遞迴演算法的運行時間通常依賴於輸入的大小 \(n\) ，以及遞迴中每一層的子問題規模和數量。一般形式可表示為一個遞迴關係式：

• \(T(n)\) ：問題大小為 \(n\) 的運行時間
• \(a\) ：每層遞迴中分解成的子問題數量
• \(b\) ：每個子問題的規模是原問題的 \(\frac{1}{b}\)
• \(f(n)\) ：在當前層進行的額外計算量（非遞迴部分）

示例#

考慮經典的 二分搜索 遞迴複雜度： [ T(n) = T\left(\frac{n}{2}\right) + O(1) ]

這裡： - \(a = 1\) ：每次遞迴只產生 1 個子問題
- \(b = 2\) ：子問題的大小是原問題的一半
- \(f(n) = O(1)\) ：非遞迴部分的額外操作為常數時間

2. 主定理 (Master Theorem)#

主定理是一種常用方法，用於求解形如 \(T(n) = aT\left(\frac{n}{b}\right) + f(n)\) 的遞迴關係式。主定理分為三種情況：

1. 情況 1： 如果 \(f(n) = O(n^{\log_b a - \epsilon})\) （其中 \(\epsilon > 0\) ），則 \(T(n) = O(n^{\log_b a})\) 。
2. 情況 2： 如果 \(f(n) = \Theta(n^{\log_b a})\) ，則 \(T(n) = O(n^{\log_b a} \log n)\) 。
3. 情況 3： 如果 \(f(n) = \Omega(n^{\log_b a + \epsilon})\) （其中 \(\epsilon > 0\) ），且 \(a f(n/b) \leq kf(n)\) for some \(k < 1\) ，則 \(T(n) = O(f(n))\) 。

示例：分治演算法#

假設 \(T(n) = 2T\left(\frac{n}{2}\right) + O(n)\) ：
- \(a = 2\) , \(b = 2\) , \(f(n) = O(n)\) 。
- \(\log_b a = \log_2 2 = 1\) 。
- \(f(n) = O(n^{\log_2 2}) = O(n)\) 。

根據 主定理的情況 2，運行時間為：
[ T(n) = O(n \log n) ]

3. 遞迴樹法#

遞迴樹法透過繪製遞迴關係的樹形結構，逐層計算每層的計算量，最後加總所有層的運算量來估計總運行時間。

示例：合併排序（Merge Sort）#

合併排序的遞迴關係式為： [ T(n) = 2T\left(\frac{n}{2}\right) + O(n) ]

• 第一層： \(O(n)\)
• 第二層： \(2 \cdot O\left(\frac{n}{2}\right) = O(n)\)
• 第三層： \(4 \cdot O\left(\frac{n}{4}\right) = O(n)\)
• 依此類推，每層的計算量都為 \(O(n)\) 。

總層數為 \(\log_2 n\) ，因此： [ T(n) = O(n \log n) ]

4. 常見遞迴關係式與其解法#

以下是一些常見遞迴關係式及其對應的時間複雜度：

5. 實戰例題：費波那契數列#

費波那契數列的遞迴定義為： [ F(n) = F(n-1) + F(n-2), \quad F(0) = 0, F(1) = 1 ]

時間複雜度分析#

• 每一層展開兩個子問題。
• 樹的高度為 \(n\) 。
• 每層的子問題數量指數增長： \(O(2^n)\) 。

因此，遞迴版本的費波那契數列運行時間為 O(2^n)，具有指數時間複雜度。

優化：動態規劃#

使用動態規劃可將時間複雜度降為 O(n)。

6. 小結#

在計算遞迴的 Big O 複雜度時，常用的方法包括： 1. 建立遞迴關係式。
2. 使用 主定理 或 遞迴樹法 來求解。
3. 理解常見的遞迴模式與複雜度。

通過上述方法，能有效分析各類遞迴演算法的時間複雜度，並根據需求進行優化。