早期历史上的先例

折半搜索算法——一个将原来问题连逐地拆细成大约一半大小的单一子问题的分治算法——拥有一段悠长历史。虽然算法在计算机上的清楚描述出现在1946年约翰莫齐利（John Mauchly）的一篇文章里，然而利用已排序的物件序列去加快搜寻的构想早已在公元前200年的巴比伦尼亚出现。另一个单一子问题的分治算法是找出2个数的最大公因数的辗转相除法（透过将数字化小至使子问题变得简单），于公元前数世纪已经出现。

一个早期有多个子问题的分治算法是高斯在1805年描述关于快速傅立叶奱换的算法，尽管他没有量化地分析它的操作数目，而快速傅立叶奱换直至在一世纪之后被重新发现之前亦没有广泛流传。这个算法现在称为库利－图基快速傅里叶变换算法。

至于专门用于计算机之上而且正确地分析的分治算法早期例子，则可以数到约翰·冯·诺伊曼于1945年发明的归并排序。

另一个显著的例子是Anatolii Alexeevitch Karatsuba于1960年发明在 O ( n log 2 ⁡ ⁡ --> 3 ) {\displaystyle O(n^{\log _{2}3})} 步骤内将两个n位数相乘的Karatsuba算法。它安德雷·柯尔莫哥洛夫哥洛夫于1956年认为这个乘法需要 Ω Ω --> ( n 2 ) {\displaystyle \Omega (n^{2})} 步骤的猜想。

高德纳举了一个最初并没有涉及计算机的分治算法例子，就是一般邮局用于分发信件的方法：信件在主要邮局根据不同的地理范围而分到不同的袋里，每个袋亦在运送到地区邮局时分到更小的袋里，如是者直至信件被派发为止。这个方法与早于1929年的打孔卡排序机所用的基数排序相类同。

优势

解决困难问题

分治算法是一个解决复杂问题的好工具，它可以把问题分解成若干个子问题，把子问题逐个解决，再组合到一起形成大问题的答案。比如，汉诺塔问题如果采用分治算法，可以把高度为n的塔的问题转换成高度为n-1的塔来解决，如此重复，直至问题化简到可以很容易的处理为止。

算法效率

人们发现有很多效率很高的分治算法，比如，Karatsuba快速乘法算法、快速排序算法和并行算法、矩阵乘法的施特拉森算法、快速傅里叶变换等。

同步性

内存存取

修正控制

实现

循环递归

在每一层递归上都有三个步骤：

分解：将原问题分解为若干个规模较小，相对独立，与原问题形式相同的子问题。

解决：若子问题规模较小且易于解决时，则直接解。否则，递归地解决各子问题。

合并：将各子问题的解合并为原问题的解。

显堆栈

示例

分治法在高级语言中主要的一个思想是递归，LISP语言中的体现出了极丰富的分治法。

以下是归并排序C语言的示例代码，输入参数中，需要排序的数组为array[],起始索引为first，终止索引为last。调用完成后，array[]中从first到last处于升序排列。

voidmerge_sort(intarray[],unsignedintfirst,unsignedintlast){intmid=0;if(first<last){mid=(first+last)/2;merge_sort(array,first,mid);merge_sort(array,mid+1,last);merge(array,first,mid,last);}}

在程式中可以看出分治法的应用：在merge_sort()中，将原来针对索引first到last的数组排序的问题，分为二份较小的问题

先针对索引first到mid的数组排序。

再针对索引mid+1到last的数组排序。

最后再进行二个数组的合并。

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。