算法基础（十一）—— 递归树如何看懂分治算法的运行时间

1. 定位导航前面已经学习了分治思想分解 → 解决 → 合并分治算法经常可以写成递归式。例如归并排序先把数组拆成左右两半 分别排序左右两半 再合并两个有序数组。它的运行时间可以粗略写成T(n)2T(n/2)n T(n) 2T(n/2) nT(n)2T(n/2)n这里的意思是2T(n/2)两个规模为n/2的子问题 n合并两个有序数组需要线性时间。问题是这个递归式最终是多少递归树就是一种非常直观的分析方法。2. 概念术语术语定义举例递归树把递归调用展开成树状结构根节点是原问题根节点原始问题规模为n的排序问题子节点递归产生的子问题两个规模为n/2的问题层数递归展开的深度每次折半大约log n层每层成本同一层所有节点成本之和归并排序每层约为n叶子节点递归基对应的问题规模为 1 的子数组总成本所有层成本之和n n ... n关键澄清递归树不是执行流程图而是成本分析图。每个节点代表一个子问题的工作量。分析时不能只看树有多深还要看每一层总成本。最后要把所有层的成本加起来。3. 什么是递归树递归树就是把递归式不断展开。比如T(n)2T(n/2)n T(n) 2T(n/2) nT(n)2T(n/2)n可以理解为一个规模 n 的问题 拆成两个规模 n/2 的问题 每个 n/2 又继续拆成两个 n/4 直到规模变成 1递归树的核心用途是把递归调用的总成本拆成一层一层来统计。4. 用递归树分析归并排序归并排序的递归式是T(n)2T(n/2)n T(n) 2T(n/2) nT(n)2T(n/2)n递归树如下观察这棵树第 0 层只有一个问题规模是n。合并成本是n nn第 1 层有两个问题每个规模是n/2。这一层总成本是n/2n/2n n/2 n/2 nn/2n/2n第 2 层有四个问题每个规模是n/4。这一层总成本是4×n/4n 4 \times n/4 n4×n/4n可以发现每一层总成本都是 n。5. 动态推演递归树如何逐层展开下面用动态图看递归树展开过程。展开过程可以理解为根节点表示原问题规模是n第一层拆成两个n/2第二层拆成四个n/4一直拆到规模为 1 的叶子每一层总成本约为n层数约为log n。6. 每层成本如何计算对于归并排序第k层有2k 2^k2k个子问题。每个子问题规模是n2k \frac{n}{2^k}2kn​所以第k层总成本是2k×n2kn 2^k \times \frac{n}{2^k} n2k×2kn​n这就是为什么归并排序每一层总成本都约为n。7. 总成本如何求和既然每层成本都是n那只需要知道有多少层。每次问题规模折半n → n/2 → n/4 → n/8 → ... → 1要折半多少次才能到 1答案大约是log⁡2n \log_2 nlog2​n所以总成本是nnn⋯n n n n \cdots nnnn⋯n一共有约log n层因此T(n)O(nlog⁡n) T(n) O(n \log n)T(n)O(nlogn)这就是递归树分析的核心套路总成本 每层成本 × 层数8. 常见递归式的递归树直觉递归树不仅能分析归并排序还能帮助理解很多递归式。8.1 T(n)T(n/2)1每层只递归到一个子问题每层额外成本是常数。层数是log n所以总成本是O(log⁡n) O(\log n)O(logn)典型例子是二分查找。8.2 T(n)2T(n/2)n每层总成本是n层数是log n。所以总成本是O(nlog⁡n) O(n \log n)O(nlogn)典型例子是归并排序。8.3 T(n)2T(n/2)1每个节点成本是常数但节点数量会越来越多。整棵树节点数大约是O(n) O(n)O(n)所以总成本是O(n) O(n)O(n)8.4 T(n)4T(n/2)n每层子问题数量增长更快。叶子层成本会变得非常大通常最后得到平方级O(n2) O(n^2)O(n2)9. 代码实践打印递归层级成本下面用 Python 模拟归并排序的递归层级成本。defrecursion_tree_cost(n):level0sizen nodes1whilesize1:cost_per_nodesize level_costnodes*cost_per_nodeprint(f第{level}层: f节点数{nodes:4}f单节点规模{size:4}f本层成本{level_cost})ifsize1:breaklevel1nodes*2size//2recursion_tree_cost(16)可能输出第 0 层: 节点数1 单节点规模16 本层成本16 第 1 层: 节点数2 单节点规模8 本层成本16 第 2 层: 节点数4 单节点规模4 本层成本16 第 3 层: 节点数8 单节点规模2 本层成本16 第 4 层: 节点数16 单节点规模1 本层成本16可以看到每层成本都是 16。如果输入规模是 16层数是log⁡2164 \log_2 16 4log2​164算上叶子层总共大约 5 层。所以总成本接近16 × 5这和n log n的直觉是一致的。10. 常见误区误区一只看递归深度递归深度只是层数不是总成本。还要看每一层做多少工作。误区二只看节点数量节点数量多不一定每层成本就大。因为子问题规模也在变小。误区三忘记叶子层成本有些递归式中叶子层可能贡献主要成本。不能随便忽略。误区四层数算错如果问题规模每次折半层数通常是O(log⁡n) O(\log n)O(logn)不是O(n)。11. 现代延伸递归树分析在实际工程里也有很多影子。场景递归树视角归并排序每层合并成本相同二分查找每层只保留一半问题快速排序递归树是否平衡决定性能并行任务拆分任务树的深度和每层负载决定吞吐MapReduce分片处理再汇总类似多层聚合大文件归并多路归并可以看成分层合并分布式查询子查询树决定整体成本比如快速排序如果每次划分都很均匀递归树比较平衡性能通常很好。但如果每次都极端不均匀递归树会退化成链状结构运行时间就会变差。这就是为什么递归树不仅能分析“总成本”也能帮助我们观察算法是否稳定。12. 思考题为什么归并排序每一层总成本都是n为什么问题每次折半时层数是log nT(n)T(n/2)1为什么是O(log n)T(n)2T(n/2)1为什么是O(n)快速排序在极端不平衡时递归树会变成什么形状13. 本篇小结本篇讲清楚了递归树分析方法。核心结论是递归树把递归式展开成层级结构每个节点代表一个子问题的成本每一层的节点成本相加就是这一层的总成本所有层成本相加就是递归算法总成本归并排序的递归式是T(n)2T(n/2)n它每层成本约为n层数约为log n所以总复杂度是O(n log n)。以后看到递归式可以先尝试问三个问题每层有多少个子问题 每个子问题规模是多少 所有层加起来是多少这就是递归树分析的主线。