如何理解分治算法？
分治算法（divide and conquer）的核心思想其實(shí)就是四個(gè)字，分而治之瞻凤，也就是將原問題劃分成 n 個(gè)規(guī)模較小撇吞，并且結(jié)構(gòu)與原問題相似的子問題，遞歸地解決這些子問題埂材，然后再合并其結(jié)果，就得到原問題的解。
分治和遞歸的區(qū)別
分治算法是一種處理問題的思想嵌牺，遞歸是一種編程技巧。
實(shí)際上，分治算法一般都比較適合用遞歸來實(shí)現(xiàn)逆粹。分治算法的遞歸實(shí)現(xiàn)中募疮，每一層遞歸都會(huì)涉及這樣三個(gè)操作：
- 分解：將原問題分解成一系列子問題；
- 解決：遞歸地求解各個(gè)子問題僻弹，若子問題足夠小阿浓，則直接求解；
- 合并：將子問題的結(jié)果合并成原問題蹋绽。
分治算法能解決的問題芭毙，一般需要滿足下面這幾個(gè)條件：
- 原問題與分解成的小問題具有相同的模式；
- 原問題分解成的子問題可以獨(dú)立求解蟋字，子問題之間沒有相關(guān)性稿蹲，這一點(diǎn)是分治算法跟動(dòng)態(tài)規(guī)劃的明顯區(qū)別，等我們講到動(dòng)態(tài)規(guī)劃的時(shí)候鹊奖，會(huì)詳細(xì)對(duì)比這兩種算法苛聘；
- 具有分解終止條件，也就是說忠聚，當(dāng)問題足夠小時(shí)设哗，可以直接求解；
- 可以將子問題合并成原問題两蟀，而這個(gè)合并操作的復(fù)雜度不能太高网梢，否則就起不到減小算法總體復(fù)雜度的效果了。
分治算法應(yīng)用舉例分析
如何編程求出一組數(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ù)雜度是 O(n^2)绿渣。那有沒有更加高效的處理方法呢？
我們用分治算法來試試燕耿。我們套用分治的思想來求數(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谭期。
private int num = 0; // 全局變量或者成員變量
public int count(int[] a, int n) {
num = 0;
mergeSortCounting(a, 0, n-1);
return num;
}
private void mergeSortCounting(int[] a, int p, int r) {
if (p >= r) return;
int q = (p+r)/2;
mergeSortCounting(a, p, q);
mergeSortCounting(a, q+1, r);
merge(a, p, q, r);
}
private void merge(int[] a, int p, int q, int r) {
int i = p, j = q+1, k = 0;
int[] tmp = new int[r-p+1];
while (i<=q && j<=r) {
if (a[i] <= a[j]) {
tmp[k++] = a[i++];
} else {
num += (q-i+1); // 統(tǒng)計(jì)p-q之間，比a[j]大的元素個(gè)數(shù)
tmp[k++] = a[j++];
}
}
while (i <= q) { // 處理剩下的
tmp[k++] = a[i++];
}
while (j <= r) { // 處理剩下的
tmp[k++] = a[j++];
}
for (i = 0; i <= r-p; ++i) { // 從tmp拷貝回a
a[p+i] = tmp[i];
}
}
