第二十二章：遞迴關係 — 動畫敘事
第二十二集 · Ch.22 遞迴關係（完結篇）
算法的時間公式
合併排序的時間複雜度為什麼是 O(n log n)？
河內塔需要幾步？
遞迴關係讓我們從演算法的「分治結構」
直接推導出它的執行時間。
河內塔需要幾步？
遞迴關係讓我們從演算法的「分治結構」
直接推導出它的執行時間。
三個經典遞迴關係
河內塔
T(n)=2T(n-1)+1
解：
n=64 片需要
18 京步！
T(n) = 2ⁿ - 1n=64 片需要
18 京步！
合併排序
T(n)=2T(n/2)+n
解：
分治的代表
T(n) = Θ(n log n)分治的代表
二分搜尋
T(n)=T(n/2)+1
解：
每次砍半
T(n) = Θ(log n)每次砍半
互動：河內塔模擬器
3
n=3 盤，共需 7 步。按「下一步」開始。
主定理（Master Theorem）
對於形如 T(n) = aT(n/b) + f(n) 的遞迴關係，主定理直接給出答案：
C1
Case 1：若 f(n) = O(n^(log_b a - ε))，則
（葉節點主導）
T(n) = Θ(n^log_b(a))（葉節點主導）
C2
Case 2：若 f(n) = Θ(n^log_b(a))，則
（每層工作量相等）
T(n) = Θ(n^log_b(a) · log n)（每層工作量相等）
C3
Case 3：若 f(n) = Ω(n^(log_b a + ε))，則
（根節點主導）
T(n) = Θ(f(n))（根節點主導）
合併排序：a=2, b=2, f(n)=n，log₂2=1，f(n)=Θ(n¹) → Case 2 → T(n)=Θ(n log n)
互動：主定理計算機
T(n) = a·T(n/b) + n^c
輸入 a, b, c 後按計算
觀念測驗
T(n) = 4T(n/2) + n，用主定理求解，結果是？
✨ 完結篇 · 小結
二十二章
全部完成！
全部完成！
從邏輯證明到機率，從圖論到遞迴，
這本書涵蓋了電腦科學數學的核心。
每一章都有自己的美，也有自己的用處。
數學是電腦科學的語言——
學好它，程式才能寫得更深。
這本書涵蓋了電腦科學數學的核心。
每一章都有自己的美，也有自己的用處。
數學是電腦科學的語言——
學好它，程式才能寫得更深。
1 / 7
本頁為動畫敘事版。看完後可前往 完整第二十二章 進行互動練習。
教材來源：Mathematics for Computer Science (Lehman, Leighton, Meyer)