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

一個例子

問題：在全美國找到個子最高的那個人

美國有2億多人，我們顯然不會把2億多人排一排，然后一個個比較。

常用策略是選出每個州的冠軍。這就是“分”的過程

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

為什么分治策略奏效？

先來看個例子：

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

顯然是9*10=90次。

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

簡單的結(jié)論

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

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