【算法分析与设计】第4篇：分治策略的理论框架与经典案例

在计算机科学中很少有比“分而治之”更自然的解题思路了。面对一个庞杂的问题先把它切成几个小块逐个击破再拼回整体——这种朴素的分割策略经过严谨的形式化之后便成了我们所说的分治范式。一个标准的分治算法由三个步骤构成分解将原问题划分为k个规模较小的同类子问题理想情况下每个子问题规模大致相等。解决递归地求解各个子问题。若子问题规模已缩小到某个阈值基情形则直接求解。合并将子问题的解组合为原问题的解。形式化地若输入规模为n分解与合并的总代价为f(n)子问题个数为a每个子问题规模为n/b则时间复杂度满足递归方程T(n)aT(n/b)f(n)——这正是上一篇中我们建立并求解的通用结构。案例一归并排序——分治的完美教学样本归并排序可以说是分治策略最直观的体现。分解阶段它将数组从中间一分为二这一步只需计算中点耗时O(1)。解决阶段递归地对左右两半分别排序产生两个规模为n/2的子问题。合并阶段用两个指针遍历两个已排序的子数组按序填入原数组耗时O(n)。由此得到递归式T(n)2T(n/2)O(n)套用主定理情形二结果是Θ(n log n)。值得强调的是归并排序的这个复杂度在所有基于元素比较的排序算法中已经达到了理论上界——比较排序的下界就是Ω(n log n)这意味着归并排序在渐进意义下是最优的。但最优是有代价的合并需要额外的辅助数组空间复杂度为O(n)。这一点与原地排序的快速排序形成对照后者的空间代价是递归调用栈的O(log n)。案例二Strassen矩阵乘法——打破常规的优化范例两个n×n矩阵相乘按定义计算需做n³次标量乘法。长久以来人们默认这就是下界直到1969年Strassen用一个精巧的分治构造打破了认知。标准的分治思路是将每个矩阵切成4个n/2×n/2的子块利用分块乘法的性质递归求解C₁₁A₁₁B₁₁A₁₂B₂₁依此类推。这会产生8次n/2规模的子问题乘法和4次矩阵加法递归式T(n)8T(n/2)O(n²)解得T(n)Θ(n³)毫无改善。Strassen的洞见在于通过构造7个巧妙的中间矩阵而非8个以增加加减法为代价换取少做一次乘法。具体而言他用7次乘法和18次加减法完成了8次乘法才能完成的任务。递归式变为T(n)7T(n/2)O(n²)解得T(n)Θ(n^{log₂7})≈Θ(n^{2.81})。这个指数log₂7≈2.807的下探在理论上意义深远它第一次证明了矩阵乘法可以比n³更快。此后数十年Coppersmith-Winograd算法及其变种将指数一路压低到约2.371逼近许多人猜测的真正下界——2。但必须指出这些更快的算法由于常数因子巨大在实际中极少使用。Strassen算法本身在n足够大时通常阈值在几十到几百之间确实有实用价值这也是理论研究反哺工程实践的典型案例。分治的边界与讨论并非所有问题都适合分治。判断一个分治算法能否带来实质优化关键看两点其一子问题之间是否真正独立——若存在重叠计算动态规划可能是更好的选择其二合并代价f(n)是否足够小——若合并本身就需要Θ(n²)而子问题规模缩减有限分治可能得不偿失。此外分治算法天然适合并行计算。子问题的独立求解特性意味着它们可以被分配到不同的计算单元上同时执行这与当代多核架构高度契合也是分治思想历久弥新的重要原因。从下一篇开始我们将进入分治的另一个精彩应用——最大子数组问题并用一个线性时间的Kadane算法与其正面交锋看看分治是否总是最优解。