【算法分析与设计】第3篇：递归方程的建立与求解方法

许多优雅的算法都建立在一个朴素的思路上把原问题拆成几个规模更小的同类子问题分别求解后再合并结果。归并排序如此快速排序如此二分查找亦如此。这种“自己调用自己”的结构叫递归而描述它的时间复杂度我们不能再用简单的循环次数累加需要引入新的工具——递归方程。递归方程的一般形式并不复杂。设T(n)为输入规模为n时的运行时间一个典型的分治递归方程形如T(n)a⋅T(nb)f(n)T(n)a⋅T(bn​)f(n)其中a是每次递归调用产生的子问题个数n/b是每个子问题的规模f(n)代表分解问题和合并子问题结果所花费的时间不含递归调用本身。我们要做的就是解出T(n)的渐进界。下面介绍三种逐步深入的分析方法。一、迭代展开法这是最直接的方法把递归式反复代入自身直到触及边界条件。以归并排序为例其递归方程为 T(n) 2T(n/2) n边界T(1)1。将T(n/2)用同样的公式展开T(n)2[2T(n/4)n/2]n4T(n/4)2nT(n)2[2T(n/4)n/2]n4T(n/4)2n继续展开k次后T(n)2kT(n/2k)k⋅nT(n)2kT(n/2k)k⋅n当n/2^k 1时递归触底此时k log₂ nT(1)1代入得T(n)n⋅1nlog⁡2nΘ(nlog⁡n)T(n)n⋅1nlog2​nΘ(nlogn)迭代展开直观易懂但遇到非均匀拆分或f(n)结构复杂时代数操作会迅速变得冗长。此时递归树是更好的选择。二、递归树法递归树的画法很简单根节点代表规模为n的原始问题其代价为f(n)从根节点分出a个子节点每个代表规模为n/b的子问题如此层层展开直到叶节点代表规模为常数的基情形。将所有层的节点代价相加即得T(n)。仍然用归并排序T(n)2T(n/2)n示意。树根代价为n第二层有2个节点每个代价n/2总和为n第三层有4个节点每个代价n/4总和仍为n。树的高度为log₂ n每层总代价均为n故T(n)n·log₂ n 叶节点代价。叶节点共2^{log₂ n}n个每个代价T(1)1总计Θ(n log n)。递归树的最大优势是直观——它能让你“看见”代价如何在各层分配尤其适合处理非均匀拆分的情形比如快速排序在最好情况T(n)2T(n/2)n与最坏情况T(n)T(n-1)n下的不同树形一目了然。三、主定理对于形如T(n)aT(n/b)f(n)的标准递归式存在一个简洁的判别法则——主定理。它通过比较f(n)与n^{log_b a}的增长阶关系直接给出T(n)的渐进界。具体分为三种情形情形一若存在常数ε0使f(n)O(n^{log_b a - ε})即f(n)的增长显著慢于n^{log_b a}则T(n)Θ(n^{log_b a})。此时叶节点的工作量占据主导。情形二若f(n)Θ(n^{log_b a}·log^k n)其中k≥0即两者增长阶相当则T(n)Θ(n^{log_b a}·log^{k1} n)。当k0时就是归并排序的情形。情形三若存在常数ε0使f(n)Ω(n^{log_b a ε})且对充分大的n满足正规性条件af(n/b)≤c f(n)(c1)则T(n)Θ(f(n))。此时根节点的工作量占据主导。应用主定理前必须核实其前提a≥1且b1为常数f(n)渐进非负且必须是严格的多项式意义下的“大于”或“小于”。如果f(n)与n^{log_b a}的比值出现对数振荡等非多项式差异主定理便无法直接使用需要回归递归树或迭代法。有了这三样工具递归算法的效率分析便不再是碰运气。下一篇文章我们将用它们去拆解分治策略中的第一个经典案例——归并排序以及它背后的通用设计范型。