主定理：算法分析中用于求解某类分治递归式时间复杂度的定理，典型形式为
(T(n)=aT(n/b)+f(n))，用来比较 (f(n)) 与 (n^{\log_b a}) 的增长速度，从而给出 (T(n)) 的渐近阶（如 (O(n\log n))、(O(n^c)) 等）。该术语在不同教材中也可能写作 Master Theorem / Master Method。
/ˈmæs.tər ˈθiː.ə.rəm/
We used the master theorem to show that merge sort runs in (O(n\log n)).
我们用主定理证明归并排序的运行时间是 (O(n\log n))。
Although the recurrence looks complicated, applying the master theorem and checking the regularity condition gives a tight asymptotic bound.
尽管递归式看起来很复杂，但应用主定理并检查正则性条件后，可以得到紧确的渐近界。
“theorem”意为“定理”，来自希腊语 theōrēma（观照、命题）；“master”在此有“总括性的、权威的”之意，表示它是解决一大类分治递归式的“总方法/主公式”。在算法教材语境里，“master”通常不指“师傅”，而强调“统领、通用”的解法框架。
Select Language