在計(jì)算機(jī)科學(xué)中，分治法是一種很重要的算法。字面上的解釋是“分而治之”，就是把一個(gè)復(fù)雜的問(wèn)題分成兩個(gè)或更多的相同或相似的子問(wèn)題，再把子問(wèn)題分成更小的子問(wèn)題……直到最后子問(wèn)題可以簡(jiǎn)單的直接求解，原問(wèn)題的解即子問(wèn)題的解的合并。這個(gè)技巧是后面要介紹的幾個(gè)高效排序算法的基礎(chǔ)，所以今天就講分治。

一個(gè)例子

問(wèn)題：在全美國(guó)找到個(gè)子最高的那個(gè)人

美國(guó)有2億多人，我們顯然不會(huì)把2億多人排一排，然后一個(gè)個(gè)比較。

常用策略是選出每個(gè)州的冠軍。這就是“分”的過(guò)程

然后再總決賽，選出全美傻大個(gè)冠軍。這就是“治”的過(guò)程。當(dāng)然各個(gè)州比賽下面也可以再繼續(xù)細(xì)分為各個(gè)縣的比賽，各個(gè)縣可以細(xì)分為各個(gè)學(xué)校的比賽。。。

為什么分治策略奏效？

先來(lái)看個(gè)例子：

聚會(huì)有10個(gè)人。如果每個(gè)人都和其他所有人打招呼，聚會(huì)一共有多少次招呼？

顯然是9*10=90次。

聚會(huì)人多嘈雜，怎么辦？把10人分到2個(gè)房間里，或者分為2組，一組5個(gè)人。 只有同組的人相互打招呼。那么每組中的5個(gè)人相互打了 4*5=20個(gè)招呼。2組一共打了20+20=40個(gè)招呼，相比10個(gè)人打90個(gè)招呼，清凈太多了！

簡(jiǎn)單的結(jié)論

分治法的設(shè)計(jì)思想是，將一個(gè)難以直接解決的大問(wèn)題，分割成一些規(guī)模較小的相同問(wèn)題，以便各個(gè)擊破，分而治之。

任何一個(gè)可以用計(jì)算機(jī)求解的問(wèn)題所需的計(jì)算時(shí)間都與其規(guī)模有關(guān)。問(wèn)題的規(guī)模越小，問(wèn)題的復(fù)雜程度降低的越多，越容易直接求解。