白话算法(2) 李恕权的故事
机械力学认为整体完全等于其部分之和，反之亦然；不管把组成整体的各部分进行多少次的分解组合，或者按照什么样的顺序进行分解组合，整体的行为始终不变。这意味着各部分之间不存在相互作用，也与自身过去的历史无关。任何部分在适当的时间到达适当的位置后，就会从这个位置开始继续完成它那完全唯一确定的行为。
——Karl Deutsch
当我们把事务分解成小的部件或小的特性时，我们其实是在努力放大或夸大那些明显的独立性，而忽视了（至少在一段时间内）组合体所具有的本质上的整体性和个体特征。我们将机体分解成器官，将骨架分解成骨骼。心理学的教学也采用了类似的方法，通过分析组成因素而给出关于思想活动的主观判断：但我们却清楚地知道判断或知识、勇气或温和、爱或恐惧并不会独立存在，而是不同程度地多方面综合在一起，或者通过关联成为一个整体。
——DArcy Thompson
为了应付不熟悉而且复杂的现象，我们会尽量
1. 获得“全面”的观点——足够广泛，可以包含我们感兴趣的所有现象——这样我们就不会感到惊讶；
2. 获得“最小”的观点——将不必区分的状态合并——这样就不会使观察的负担过重；
3. 获得“独立”的观点——将观察到的状态分解成不相干的部分——这样就可以减少对脑力的要求。
——温伯格 《系统化思维导论》
倒推分解
一九七六年的冬天，李恕权当时十九岁，在休士顿太空总署的太空梭实验室里工作，同时也在总署旁边的休士顿大学主修电脑。纵然忙于学校、睡眠与工作之间，这几乎占据了他一天二十四小时的全部时间，但只要有多余的一分钟，他总是会把所有的精力放在音乐创作上。
李恕权深知写歌词不是自己所擅长的，所以通过一番努力，终于找到了一个好搭档，她的名字叫做凡內芮（Valerie Johnson）。
一个星期六的周末，凡內芮热情地邀请他至她家的牧場烤肉。凡內芮知道他对音乐有着无比的执着与热情，然而，面对那遥远的音乐界及整个美国陌生的唱片市场，他们一点管道都没有。他们坐在德州的乡下，不知道下一步该如何走。突然间，凡內芮冒出了一句话：
“想像你五年后在做什么？”
李恕权沉思了几分钟，开始告诉她：“第一，五年后，我希望能有一张唱片在市场上，而这张唱片很受欢迎，可以得到许多人的肯定。第二，我住在一个有很多很多音乐的地方，能天天与一些世界一流的乐师一起工作。”
凡內芮说：“好，既然这样，我们就把这个目标倒算回来。如果第五年，你有一张唱片在市场上，那么你的第四年一定是要跟一家唱片公司签上合约。”
“那么你的第三年一定是要有一个完整的作品，可以拿给很多很多的唱片公司听，对不对？”
“那么你的第二年，一定要有很棒的作品开始录音了。”
“那么你的第一年，就一定要把你所有要准备录音的作品全部编曲，排练就位准备好。”
“那么你的第六个月，就是要把那些没有完成的作品修饰好，然后让你自己可以逐一筛选。”
“那么你的第一个月就是要把目前这几首曲子完工。”
“那么你的第一个礼拜就是要先列出一整个清单，排出哪些曲子需要修改，哪些需要完工。”
“好了，我们现在不就已经知道你下个星期一要做什么了吗？”凡內芮笑笑说。
“喔，对了。你还说你五年后，要生活在一个有很多音乐的地方，然后与许多一流的乐师一起忙着工作，对吗？”她急忙地补充说。“如果，你的第五年已经在与这些人一起工作，那么你的第四年照道理应该有你自己的一个工作室或录音室。那么你的第三年，可能是先跟这个圈子里的人在一起工作。那么你的第二年，应该不是住在德州，而是已经住在纽约或是洛杉机了。”
次年(一九七七年)，李恕权辞掉了令许多人羨慕的太空总署的工作，离开了休士顿，搬到洛杉机。
不敢说是恰好五年，但大约可说是第六年。一九八三年，李恕权的唱片在亚洲开始销起來，他一天二十四小時几乎全都忙着与一些顶尖的音乐高手，日出日落地一起工作。
如果……就能……
叫兽：“请同学们用如果……就能……造句”。
阿基米德：“如果给我一个支点，我就能撬起整个地球”。
程序员甲：“如果L是一个有序的数组，就能把它与另一个数字b合并成一个新的有序的数组”（插入排序）。
冯·诺伊曼：“如果L、R都是有序的数组，就能把它们合并成一个新的有序的数组”（归并排序）。
李恕权：“如果第四年能跟一家唱片公司签上合约，第五年就很可能可以出唱片”。
叫兽：“你怎么有点底气不足啊？”
李恕权：“因为生活可能会欺骗我，但计算机不会。”
递归分解
当问题太过复杂而无法直接求解时，一个最简单的方法就是，把问题分解成相互独立的子问题分别求解，再想办法把子问题的解合并成整个问题的解。如果子问题还是比较复杂而无法直接求解，可以再次对其进行分解，就像李恕权所做的那样。不过对于算法来说，由于通常输入的元素个数（或者说计算的复杂度）是不确定的，导致我们无法确定需要分解多少次才能把子问题简化到可以直接求解的程度，所以我们在做分解的时候不能像李恕权那样自由，一般来说都必须让子问题与原问题具有相似的结构、只是规模较小，这样才能递归地进行分解、解决。这种先分解再合并的解决问题的方法，就叫做分治法(divide-and-conquer)。
分治法
分解(Divide)：将原问题分解成一系列子问题；
解决(Conquer)：递归地解决各子问题。若子问题足够小，则直接求解；
合并(Combine)：将子问题的结果合并成原问题的解。
分治版插入排序
回顾一下上一篇介绍的使用增量(incremental)方法的插入排序，可以用一句话来概括其思路：“因为可以把子数组L处理成有序的，所以能进一步把L与一个元素b合并成新的有序的数组……”。下面让我们来实现一个分治版的插入排序，用一句话来说就是：“把输入分解成一个子数组L和一个元素b，如果可以把L处理成有序的，就能把L和b合并成新的有序的数组……”。
分解：将n个元素分解成n-1个元素的子数组L和一个元素b；
解决：用插入排序法对L递归地排序；
合并：把L与b合并成新的有序的数组。
分治版的插入排序函数名为DCInsertionSort()，代码如下
