递归树法

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

图中 $T(n)=2T(n/2)+n$ 的每个内部层成本都是 $2^i(n/2^i)=n$。有 $h={\log }_{2}n$ 个内部层，另有 $2^h=n$ 个叶，所以 $T(n)=n{\log }_{2}n+cn=\mathrm{\Theta }(n\log n)$。例如 $n=8,c=1$ 时，规模为 $8,4,2$ 的三层各花 $8$，叶层也花 $8$，总成本 $32$。这里“每层都是 $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$ 中，每次分裂保持子问题总规模不变，但沿 $1/3$ 分支会更早到叶。完整展开的前 $\mathrm{\Theta }(\log n)$ 层各有线性成本，任何一层仍活动的节点规模总和不超过 $n$，最长路径也只有 $O(\log n)$ 层；在常数基例与通常取整约定下得到 $\mathrm{\Theta }(n\log 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 操作数。三者都能画树，但参数、叶成本和资源单位不同。