遞迴關係式與主定理

主定理情況一(master-theorem case 1)

想像 T(n) = a T(n/b) + f(n) 的遞迴樹。如果往下走向眾多葉子時,工作量堆積的速度快過合併步驟所能跟上的速度,那麼樹的底部就承載了幾乎全部成本。情況一就是「葉子勝出」的情形。

形式上,情況一適用於:存在某常數 epsilon > 0,使得 f(n) = O(n^(log_b a - epsilon))——也就是合併工作在多項式意義上比臨界項 n^(log_b a)「更小」。此時 T(n) = Theta(n^(log_b a))。透過樹來看直覺:共有 a^(log_b n) = n^(log_b a) 個葉子,每個做 Theta(1) 的工作,所以光是葉子就貢獻 Theta(n^(log_b a));又因為越上層做的工作呈幾何級數遞減,整棵樹便由這個葉子總量主導。關鍵字是 epsilon:f 必須小一個「真正的 n 的次方」,而不只是小一個對數。

對於「製造很多子問題、合併又便宜」的遞迴式,這就是其所屬情況。史特拉森演算法 T(n) = 7 T(n/2) + Theta(n^2),其 log_2 7 ≈ 2.807,且 n^2 = O(n^(2.807 - epsilon)),所以情況一給出 Theta(n^(log_2 7)) ≈ Theta(n^2.81)——比樸素的 Theta(n^3) 更快。誠實的告誡:你必須驗證這個差距是多項式的。若 f(n) 是 n^(log_b a) / log n,它雖比臨界項小,卻不是小一個 n 的次方,所以情況一「不」適用,你落在縫隙裡。

T(n) = 8 T(n/2) + Theta(n^2):log_2 8 = 3,且 f(n) = n^2 = O(n^(3 - 1)),所以差距 epsilon = 1 > 0 成立。情況一給出 T(n) = Theta(n^3)。n^2 的合併被 n^3 的葉子完全壓過。

若 f(n) 比 n^(log_b a) 小一個 n 的次方,則葉子主導:T = Theta(n^(log_b a))。

「較小」必須是多項式意義的:f(n) = O(n^(log_b a - epsilon)) 且 epsilon 嚴格為正。只小一個對數因子(例如 f = n^(log_b a)/log n)並不夠,會讓你落入定理無法解決的縫隙。

又稱
leaf-dominated casecase 1葉子主導情況