其实任何一个可以用程序求解的问题所需的计算时间都与其规模与复杂度有关,问题的规模越小,越容易直接求解,因此可以使子问题的规模不断缩小,直到这些子问题简单到可以解决,最后将各个子问题的解合并,得到原问题的答案。
举个例子来说,如果你被委托制作一个项目的计划书,这个计划书有8个章节的主题,只靠一个人独立完成,不但会花较长时间,而且计划书中有些主题的内容也有可能不是自己的专长,这个时候就可以按照这8个章节的特性分工给2位项目专员去完成。不过,为了让计划书更快完成,可以找到适合的分类,再分别将其分割成2章一组,并分配给更多不同的项目专员。如此一来,每位项目专员只需负责其中的2个章节。经过这样的分配,就可以将原先的大计划书简化为4个小项目,再委托给4位项目专员去完成。以此类推,上述问题的解决方案示意图如图3-2所示。
图3-2 用分治法将大项目分割为子项目来
分治法也可以应用在数字的分类与排序上,例如要以人工的方式将散落在地上的打印稿从第1页开始整理并排序到第100页。我们有两种方法,一种方法是逐一捡起打印稿,并逐一按页码顺序插入正确的位置。但是,这样的方法有一个缺点,就是排序和整理的过程较为繁杂,而且较花时间。
另一种方法是应用分治法的原理,先将页码1到页码10放在一起,再将页码11到页码20放在一起,以此类推,最后将页码91到页码100放在一起。也就是说,将原先的100页分类为10个页码区间,然后我们分别对10堆页码进行整理,最后将页码从小到大的分组合并起来,就能较为轻松地恢复到原先的稿件顺序。通过分治法,我们可以让原先复杂的问题变成规则更简单、数量更少且更容易解决的小问题。