主定理

主定理比较递归树每层子问题总成本 $af(n/b^i)$ 与叶子总量 $n^{{\log }_{b}a}$，总成本由叶子数量、各层均摊成本或根部合并工作中的主导者决定。三种主情形分别对应叶子占优、各层同阶和根部非递归工作占优；正则条件防止 $f$ 在缩放时异常振荡。它是快速识别模板，不是所有递归式的万能求解器。

归并排序的递推 $T(n)=2T(n/2)+n$ 满足 $n^{{\log }_{2}2}=n$；各层成本均为 $n$，共有 $\log n$ 层，故 $T(n)=\mathrm{\Theta }(n\log n)$。作为另外两类的对照，$T(n)=T(n/2)+1$ 得 $\mathrm{\Theta }(\log n)$，而 $T(n)=4T(n/2)+n$ 由叶子项 $n^2$ 占优得 $\mathrm{\Theta }(n^2)$。

$T(n)=T(n/2)+T(n/3)+n$ 子问题规模不统一，不符合模板；$f(n)=n^{{\log }_{b}a}\log \log n$ 等边界函数需扩展版本或其他方法。向上/下取整通常不改变渐近阶，但仍需满足基本条件。

它以 分治法公理库分治法Divide and conquer把问题分成较小同类子问题，递归求解后合并结果的算法设计范式。 和 渐近记号公理库渐近记号Asymptotic notation · Big O notation忽略常数和低阶项，比较函数在输入趋于无穷时的增长速度。 为背景，递归树法公理库递归树法Recursion-tree method把递归式各层代价展开成树并对层和叶子求和的渐近分析方法。 解释三种情形，代入法公理库递归式代入法Substitution method for recurrences先猜测渐近界再用归纳代入验证并调节常数的方法。 可验证猜测。Akra–Bazzi 定理处理不等规模子问题，是常见延伸。

Master theorem 只处理 $aT(n/b)+f(n)$ 型规则分治。缓存无关模型公理库缓存无关模型Cache-oblivious model算法代码不使用缓存参数，但在理想缓存中对所有块尺度分析 miss。还需为同一递归计算块传输，CPU 递推不能替代 cache recurrence；Work–Depth 模型公理库Work–Depth 模型work-depth model · work-span model · computation DAG model把并行计算表示为依赖 DAG，以总工作 W 和关键路径深度 D 分离工作量与并行性。分别计算总工作和关键路径，不能只用串行 $T(n)$ 推并行时间。精确指数算法中的Measure and Conquer公理库Measure and Conquermeasure and conquer · 测度与征服用按局部状态加权的非整数测度分析分支算法，并联合优化所有规则的指数底数。按非标准 measure 分析不等分支，常见 $T(k)=T(k-d_1)+T(k-d_2)$ 也不属于 Master theorem 三类。