如何理解分治算法
分治算法（divide and conquer）的核心思想就四個(gè)字：分而治之夭坪，就是將原問題劃分成 n 個(gè)規(guī)模較小，并且結(jié)構(gòu)與原問題相似的子問題可很，遞歸地解決這些子問題橱乱，然后再合并其結(jié)果俱病，就得到原問題的解。
這個(gè)定義看起來(lái)有點(diǎn)類似遞歸的定義搂漠。分治和遞歸的區(qū)別是迂卢，分治算法是一種處理問題的思想，遞歸是一種編程技巧桐汤。實(shí)際上而克，分治算法一般比較適合用遞歸來(lái)實(shí)現(xiàn)。
分治算法的遞歸實(shí)現(xiàn)中怔毛，每一層遞歸都會(huì)涉及三個(gè)操作：
- 分解：將原問題分解成一系列子問題员萍；
- 解決：遞歸地求解各個(gè)子問題，若子問題足夠小拣度，則直接求解碎绎；
- 合并：將子問題的結(jié)果合并成原問題；
分治算法能解決的問題抗果，一般需要滿足下面這幾個(gè)條件：
- 原問題與分解成的小問題具有相同的模式筋帖；
- 原問題分解成的子問題可以獨(dú)立求解，子問題之間沒有相關(guān)性窖张；
- 具有分解終止條件幕随；
- 可以將子問題合并成原問題，并且這個(gè)拿著操作的復(fù)雜度不能太高宿接；
分治算法應(yīng)用舉例分析
假設(shè)我們有 n 個(gè)數(shù)據(jù)赘淮，我們期望數(shù)據(jù)從小到大排列，那完全有序的數(shù)據(jù)的有序度就是 睦霎，逆序度等于0梢卸；相反，倒序排列的數(shù)據(jù)的有序度就是0副女，逆序度是
蛤高。除了這兩種 極端情況外，我們通過計(jì)算有序?qū)蛘吣嫘驅(qū)Φ膫€(gè)數(shù)，來(lái)表示數(shù)據(jù)的有序度或逆序度戴陡。
如何編程求出一組數(shù)據(jù)的有序?qū)€(gè)數(shù)或者逆序?qū)€(gè)數(shù)呢塞绿？
最笨的方法是，拿每個(gè)數(shù)字跟它后面的數(shù)字比較恤批，看有幾個(gè)比它小的异吻。我們把比它小的數(shù)字 個(gè)數(shù)記作 k，通過這樣的方式喜庞，把每個(gè)數(shù)字都考察一遍之后诀浪，然后對(duì)每個(gè)數(shù)字對(duì)應(yīng)的k值求 和，最后得到的總和就是逆序?qū)€(gè)數(shù)延都。不過雷猪，這樣操作的時(shí)間復(fù)雜度是 。
套用分治思想來(lái)求數(shù)組A的逆序?qū)€(gè)數(shù)晰房。我們可以將數(shù)組分成 前后兩半 A1 和 A2求摇，分別計(jì)算A1和A2的逆序?qū)€(gè)數(shù) K1 和 K2，然后再計(jì)算A1與A2之間的逆序?qū)?個(gè)數(shù) K3嫉你。那數(shù)組A的逆序?qū)€(gè)數(shù)就等于 K1+K2+K3月帝。
使用歸并排序算法來(lái)快速計(jì)算出兩個(gè)子問題 A1 與 A2 之間的逆序?qū)€(gè)數(shù)。求解過程如下圖：
代碼實(shí)現(xiàn)：
var num = 0 // 全局變量或者成員變量
func count(a []int, n int) int {
num = 0
mergeSortCounting(a, 0, n-1)
return num
}
func mergeSortCounting(a []int, p int, r int) {
if p >= r {
return
}
q := (p + r) / 2
mergeSortCounting(a, p, q)
mergeSortCounting(a, q+1, r)
merge(a, p, q, r)
}
func merge(a []int, p int, q int, r int) {
i, j, k := p, q+1, 0
tmp := make([]int, r-p+1)
for i <= q && j <= r {
if a[i] <= a[j] {
tmp[k] = a[i]
k++
i++
} else {
num += (q - i + 1) // 統(tǒng)計(jì)p-q之間幽污，比a[j]大的元素個(gè)數(shù)
tmp[k] = a[j]
k++
j++
}
}
for i <= q { // 處理剩下的
tmp[k] = a[i]
k++
i++
}
for j <= r { // 處理剩下的
tmp[k] = a[j]
k++
j++
}
for i := 0; i <= r-p; i++ { // 從tmp拷貝回a
a[p+i] = tmp[i]
}
}
分治思想在海量數(shù)據(jù)處理中的應(yīng)用
分治算法思想的應(yīng)用是非常廣泛的,并不僅限于指導(dǎo)編程和算法設(shè)計(jì)嚷辅。它還經(jīng)常用在海量數(shù)據(jù)處理的場(chǎng)景中。前面講的數(shù)據(jù)結(jié)構(gòu)和算法距误，大部分都是基于內(nèi)存存儲(chǔ)和單機(jī)處理簸搞。但是，如果要處理的數(shù)據(jù)量非常大准潭，沒法一次性放到內(nèi)存中趁俊，這個(gè)時(shí)候，這些數(shù)據(jù)結(jié)構(gòu)和算法就無(wú)法工作了刑然。
比如寺擂，給 10GB 訂單文件按照金額排序，而機(jī)器的內(nèi)存可能只有 2泼掠、3GB怔软，無(wú)法一次性加載到內(nèi)存，就無(wú)法單純地使用快排择镇、歸并等基礎(chǔ)算法來(lái)解決了挡逼。
要解決這種數(shù)據(jù)量大到內(nèi)存裝不下的問題，可以使用分治思想腻豌。將海量的數(shù)據(jù)集合劃分成幾個(gè)小的數(shù)據(jù)集合家坎，每個(gè)小的數(shù)據(jù)集合能夠單獨(dú)加載到內(nèi)存來(lái)解決嘱能，然后再將小數(shù)據(jù)集合合并成大數(shù)據(jù)集合。
比如剛剛舉的那個(gè)例子虱疏，給 10GB 的訂單排序惹骂，我們就可以先掃描一遍訂單，根據(jù)訂單的金 額订框，將 10GB 的文件劃分為幾個(gè)金額區(qū)間析苫。比如訂單金額為 1 到 100 元的放到一個(gè)小文件，101 到 200 之間的放到另一個(gè)文件穿扳，以此類推。這樣每個(gè)小文件都可以單獨(dú)加載到內(nèi)存排序国旷，最后將 這些有序的小文件合并矛物，就是最終有序的 10GB 訂單數(shù)據(jù)了。
