递归树法

递归树把递推式分散的工作展开成按深度排列的子问题，分别计算每层非递归工作和叶子成本，再求和。观察每层工作是递增、递减还是同阶，往往能直接看出总成本由根、所有层还是叶子主导；它比直接套公式更直观，也能处理部分不规则递归。但必须正确跟踪每层节点数、子问题规模和停止深度；这棵树是成本展开图，不一定对应算法真实存储的递归树。

$T(n)=2T(n/2)+n$ 的第 $i$ 层有 $2^i$ 个规模 $n/2^i$ 的节点，每层工作总和 $n$，共 $\log n$ 层，故 $\mathrm{\Theta }(n\log n)$。$T(n)=3T(n/2)+n$ 的第 $i$ 层成本为 $n(3/2{)}^i$，靠近叶层占优，结果为 $\mathrm{\Theta }(n^{{\log }_{2}3})$。

作为对照，$T(n)=T(n/2)+n$ 的层成本构成几何级数，总计 $\mathrm{\Theta }(n)$；非均匀递推 $T(n)=T(n/3)+T(2n/3)+n$ 也可画树，但深度不齐，需按路径或总规模仔细求和。递归树中节点数不能只乘“层数”，因为每层子问题大小会变化。

子问题不等规模时不能只写“每层节点翻倍”；需按实际分支加总。递归式中的取整、边界条件和叶成本也可能影响低阶项，若猜出结果仍最好用代入法做严格验证。

递归关系公理库递推关系Recurrence relation用先前项规定序列当前项的关系。给出展开对象，渐近记号公理库渐近记号Asymptotic notation · Big O notation忽略常数和低阶项，比较函数在输入趋于无穷时的增长速度。给出求和结果。主定理公理库主定理Master theorem · Master method比较递归子问题总量与合并成本，快速求解一类分治递推式的渐近界。封装规则分治树，代入法公理库递归式代入法Substitution method for recurrences先猜测渐近界再用归纳代入验证并调节常数的方法。则严格证明树形直觉得到的界。递归树本身只是一种成本展开，不预设成本必须是多项式。

有界搜索树公理库有界搜索树Bounded search tree对局部障碍作完备分支，并让参数预算在每条分支严格下降。按参数 $k$ 展开分支，常得到 $T(k)=\sum _{i}T(k-d_i)+\mathrm{poly}(n)$；测度与征服公理库Measure and Conquermeasure and conquer · 测度与征服用按局部状态加权的非整数测度分析分支算法，并联合优化所有规则的指数底数。进一步为不同状态赋权，改变每条分支的有效下降量。缓存无关模型公理库缓存无关模型Cache-oblivious model算法代码不使用缓存参数，但在理想缓存中对所有块尺度分析 miss。中的递归分解还要按块传输求和，层成本不再只是 RAM 操作数。三者都能画树，但参数、叶成本和资源单位不同。