分而治之Divide and Conquer

把大问题拆成同类小问题，逐个求解，再按规则合回完整答案。

2019年温网男单冠军，是先决出各个小组的胜者，再让胜者相遇产生的。7月14日，在伦敦全英草地网球俱乐部的中央球场，德约科维奇击败费德勒，捧起奖杯。回看签表，128名选手分处上下两个半区，两人各自从一个半区晋级。半区继续分成更小的组，直到最小的一组只剩两人，打一场比赛就有答案。每组胜者向上一轮汇合，决赛再把两个半区的结果合成一个冠军。

为什么成立

每次拆分都保留同一种问题

给8个乱序数字排序，可以先各排好左右4个，再合成一列。每半又拆成两份，直到每份只剩一个数字，天然有序。每次要做的都是排序，只是规模更小。分而治之就沿着这个结构，先向下拆，再从最小的答案向上合。

合并规则保证小答案能拼成大答案

合并两列已经排好的数字时，只要比较各列最前面的数字，把较小的取走，反复做下去。因为每列后面的数字都不小于它的首项，这次取出的就是剩余数字中最小的。拆分能否成立，关键在于小答案是否保留了合成完整答案所需的信息。两列各自排好还不够，合并这一步才保证整体有序。

节省多少工作取决于拆分与合并的代价

把归并排序的工作量记作 $T (n)$ ，当 $n$ 是2的整数次幂时：

$T (n) = 2 T (n /2) + Θ (n)$

白话说，总工作量等于排好两个半份的工作，再加上随数字数量成比例的拆分与合并工作。 $Θ (n)$ 表示这一部分按线性规模增长。每层合并共处理 $n$ 个数字，合并共有 $lo g_{2} n$ 层，因此总工作量是 $Θ (n lo g n)$ 。收益来自这种安排减少了比较次数；一个人依次做完所有步骤，也能得到这个收益。

出处

分而治之在计算机科学中被系统化为算法设计方法，没有唯一的发明者。冯·诺依曼在1945年提出的归并排序是早期经典；库利与图基在1965年发表的快速傅里叶变换算法，则展示了把大计算拆成同类小计算能带来多大的效率提升。

换个领域看

技术

把长计算拆短

1965年，IBM的库利与普林斯顿大学、贝尔实验室的图基共同发表快速傅里叶变换算法。在处理长度为2的整数次幂的数据时，可以把奇数位置与偶数位置的数据分开，各做一次较小的变换，再按数学规则合成完整结果。对子序列继续这样拆，计算量便从平方级降到 $n lo g n$ 级，算出的仍是同一个离散傅里叶变换。

投资

逐层估值再合并

假设你研究一家经营食品和日用品的集团，可以先拆成两块业务，再各自按产品线继续拆小。每条产品线用适合其风险的折现率，把未来现金流换算成今天的价值，再逐层相加。总部费用的现值在集团层扣一次，最后减去净债务，得到股权价值。合并规则写清共享费用归谁扣，小估值才能拼成完整估值。

个人生活

分箱清点藏书

假设你搬家后要核对八箱书是否全部到齐，可以先分成两组，每组再分成两箱，最后逐箱核对书单。每箱留下已到数量和缺书名单，向上合并时，数量相加，名单汇总。你每次只盯一箱，最后仍能回答全部书是否到齐。打包时，每本书只登记在一张箱单上，核对时就不会重复计入。

遇事时问自己

这个大问题能否拆成几个规模更小、仍用同一种办法求解的问题？
拆到多小时，我能直接给出答案？
每个小答案必须留下哪些信息，才能合成完整答案？
跨部分的关系、共享成本和重复项目，在哪一步处理？
加上拆分、协调与合并的工作后，总工作量真的减少了吗？

边界与误用

当各部分的选择会互相改变结果，而且合并时无法补回这些影响，拆开求解就会丢掉整体答案。例如，投资组合里每只资产单独看都不错，合在一起却会共同暴露于同一种风险；风险不能按单项简单相加。最常见的误用是把任务分给不同部门，就认定已经解决了问题，却没写清结果怎样接起来。拆得过细、各份规模严重失衡，或合并比原任务还费力时，效率收益也会消失。

练一练

运维人员要从一周的记录中找出最长连续断线分钟数。记录按时间排列，每分钟只有“在线”或“断线”两种状态。他把记录不断对半切分，直到每份只剩一分钟，再逐层合并摘要。连续断线可能跨过切分点。

每份摘要保留哪组信息，才能在合并时准确算出答案？

研究员要从4096条债券报价中找出最高到期收益率，只比较已经算好的收益率数值，各条数值不同。原办法是从头扫描，共比较4095次。新办法不断均分报价，各组留下最高值，再逐层比较组内赢家。全部步骤仍由他一个人依次完成。

关于新办法的比较次数，哪种判断最站得住？

一座城市让南北两区分别优化交通信号，目标都是减少车辆等待时间。车辆会跨区行驶，两区还共用两座桥。各区只向市里提交自己的最佳配时表和最低等待时间。市里准备直接拼接两张表，宣布得到全城最优方案。

对这个结论，哪种判断最站得住？