主定理

递归树法理路递归树法Recursion-tree method把递归式各层代价展开成树并对层和叶子求和的渐近分析方法。把第 $i$ 层展开为 $a^i$ 个规模 $n/b^i$ 的子问题，所以该层的非递归成本是

共有 $h={\log }_{b}n$ 个内部层，叶子总成本为 $a^h{c}_0=c_0{n}^d$。

当 $f$ 比 $n^d$ 小一个多项式因子时，靠近叶层的工作主导；当它具有同一临界幂次时，需要累加各层的对数项；当根部成本更大且缩放受控时，各层成本向下几何衰减。主定理把这些求和结果整理成可复用的模板。

$T(n)=2T(n/2)+n$ 属于第二类，得到 $\mathrm{\Theta }(n\log n)$。$T(n)=4T(n/2)+n$ 的临界幂次为 $n^2$，属于第一类，得到 $\mathrm{\Theta }(n^2)$。$T(n)=2T(n/2)+n^2$ 属于第三类，且 $2(n/2{)}^2=n^2/2$ 满足正则条件，也得到 $\mathrm{\Theta }(n^2)$。后两式阶相同，主导工作的层次却不同。

二分型递推 $T(n)=T(n/2)+1$ 的 $d=0$，仍属于第二类，结论为 $\mathrm{\Theta }(\log n)$。若 $f(n)=n^d\log \log n$，它不落在这里列出的固定非负对数幂情形；若有 $T(n/2)+T(n/3)$ 两种分割规模，也已超出单一 $b$ 的模板。

非负成本和正基例共同保住叶子下界。例如 $T(1)=1$、$a=b=2$，却取 $f(2)=-2$、后续幂点上的 $f(n)=0$，就会得到 $T(2)=T(4)=\cdots =0$。“最终非负”本身不能排除这种早期抵消；算法运行成本应在进入所用基例以上的全部层都采用非负费用。

归并排序的上下取整递推可通过夹逼或归纳取得相同的 $n\log n$ 界。这里起作用的是实际递推的规模控制与基例，不能只把下取整符号擦掉就当作证明。

分治算法理路分治法Divide and conquer把问题分成较小同类子问题，递归求解后合并结果的算法设计范式。常先导出规则递推，再检查它落在哪一类。代入法理路递归式代入法Substitution method for recurrences先猜测渐近界再用归纳代入验证并调节常数的方法。可以验证猜测并处理取整、边界或附加项；Akra–Bazzi 方法则处理更一般的不等规模分支。

成本单位同样需要保持一致。缓存无关模型理路缓存无关模型Cache-oblivious model算法代码不使用缓存参数，但在理想缓存中对所有块尺度分析 miss。为块传输建立自己的递推，Work–Depth 模型理路Work–Depth 模型work-depth model · work-span model · computation DAG model把并行计算表示为依赖 DAG，以总工作 W 和关键路径深度 D 分离工作量与并行性。分别建立总工作和关键路径递推；串行时间的解不会自动替代这些资源。精确指数算法中按参数下降量写出的 $T(k)=T(k-d_1)+T(k-d_2)$，也应使用相应的分支分析。