電子發(fā)燒友App
介紹
分治法是計(jì)算機(jī)科學(xué)中很重要的一種思想。英文為Divide and Conquer，直譯即為分治，或者分而治之。直觀的理解就是將一個(gè)大而難的問(wèn)題分解為一些小而易的問(wèn)題，先解決這些易于解決的小問(wèn)題，再合并這些小問(wèn)題的解（合并可以是分別求出小問(wèn)題的解再合并，或者是直接將相同的小問(wèn)題合并只求解一次），從而得到大問(wèn)題的解。需要注意的是小問(wèn)題必須和大問(wèn)題是同一個(gè)類型的問(wèn)題，或者說(shuō)解法相同，這樣才可以遞歸求解。我們發(fā)現(xiàn)，這種實(shí)際上是自頂向下地分解問(wèn)題。
我們可以說(shuō)分治思想是被極廣泛運(yùn)用的思想。
很多算法和數(shù)據(jù)結(jié)構(gòu)采用了這種思想。另外計(jì)算機(jī)圖像渲染將像素點(diǎn)分配給GPU內(nèi)的多個(gè)流處理器分別處理，最后合成出一幀的圖像；也會(huì)將一個(gè)矩陣乘法分解成n個(gè)部分分配給n個(gè)處理器并行處理。
下面介紹一些采用了分治思想的算法和數(shù)據(jù)結(jié)構(gòu)。
算法
快速排序
數(shù)列每次按小于某個(gè)數(shù)（可能是數(shù)列的首尾元素或者是隨機(jī)選擇或者是三值取中法等）的和大于某個(gè)數(shù)的標(biāo)準(zhǔn)劃分為兩個(gè)子序列，但子序列內(nèi)的順序和在原數(shù)列內(nèi)的順序一樣，時(shí)間復(fù)雜度期望nlogn
歸并排序
將數(shù)列從中間切成兩半，分別遞歸解決兩半的排序問(wèn)題，再合并解，即合并兩個(gè)有序數(shù)列，由于每次合并需要花費(fèi)O(n)的時(shí)間，因此時(shí)間復(fù)雜度為O(nlogn)。
為了能更好地理解分治的思想，我們?cè)敿?xì)介紹一下歸并排序。
比如我們定義mergeSort(array: list, from: int, to: int)為歸并排序函數(shù)，那么我們可以這么寫：
join(a: list, b) =if(either a or b is empty) b or aelseif(a[1] < b[1]) [a[1]] + join(a[2:], b)else[b[1]] + join(a, b[2:])mergeSort(array) = join(mergeSort(array[1:mid]), mergeSort(array[mid+1:]))wheremid = length(array) /2
join函數(shù)表示合并兩個(gè)有序數(shù)列，復(fù)雜度為O(n)，意思就是有兩個(gè)指針i和j一開(kāi)始分別指向a和b的首元素。這是i和j之前的元素都已經(jīng)被檢查過(guò)了，如果a[i]
如果我們?cè)诩埳袭嫵鲞f歸的過(guò)程：
|---------------| |0000| |---------------| |11|22| |-------|-------| |3|4|5|6| |---|---|---|---|
數(shù)字表示遞歸方法的節(jié)點(diǎn)編號(hào)。
遞歸的層數(shù)最多是log2n，對(duì)于每個(gè)元素都被訪問(wèn)了O(log2n)次，因此時(shí)間復(fù)雜度為O(nlogn)。
到這里讀者可能會(huì)想到log的底（或者是每次劃分的子問(wèn)題個(gè)數(shù)）是不是越大越好呢？顯然不是，應(yīng)該與實(shí)際問(wèn)題相適應(yīng)。如果劃分的子問(wèn)題數(shù)過(guò)多，那么合并子問(wèn)題的時(shí)候就會(huì)導(dǎo)致麻煩。比如歸并排序的有序數(shù)列合并，我們之前認(rèn)為的O(n)的合并是基于劃分2次的。如果我們令劃分的子序列數(shù)為b，那么最終的時(shí)間復(fù)雜度是O(bnlogbn)。我們將其可以寫成
O(nlnnblnb)
我們發(fā)現(xiàn)blnb的最小值點(diǎn)為x=e，也就在2~3之間，而且x=2和x=3的函數(shù)值相差不大，也就是說(shuō)我們劃分成2個(gè)子問(wèn)題或者劃分成3個(gè)子問(wèn)題的時(shí)候，效率是最高的。另一方面，劃分成2個(gè)子問(wèn)題的程序比3個(gè)的要更好實(shí)現(xiàn)，因此我們一般在分治的時(shí)候?qū)?wèn)題劃分為2個(gè)子問(wèn)題。當(dāng)然在必要時(shí)可能會(huì)有其他劃分方法。
快速傅里葉變換
處理多項(xiàng)式的乘法，分解多項(xiàng)式并應(yīng)用復(fù)數(shù)的對(duì)稱和周期性減少重復(fù)計(jì)算
快速冪
將求n次冪分為2個(gè)n/2次冪的較小問(wèn)題，而兩個(gè)小問(wèn)題是相同的，求出一個(gè)就知道另外一個(gè)的解
（在樹(shù)上的分治）
……
數(shù)據(jù)結(jié)構(gòu)
實(shí)際上很多基于樹(shù)的數(shù)據(jù)結(jié)構(gòu)都可以認(rèn)為采用了分治思想，但分治不代表一定是簡(jiǎn)單的二分。
線段樹(shù)
數(shù)列每次對(duì)半切割，區(qū)間查找被劃分為幾個(gè)已有的線段樹(shù)節(jié)點(diǎn)的并。
線段樹(shù)是最基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)之一，這里較詳細(xì)地講一下。譬如給定一個(gè)數(shù)列1, 2, 3, 4，構(gòu)造這個(gè)數(shù)列的線段樹(shù)。
結(jié)果如下：
|---------------|| 1 2 3 4 ||---------------|| 1 2 | 3 4 ||---------------|| 1 | 2 | 3 | 4 ||---------------|
看起來(lái)和歸并排序的遞歸過(guò)程很像。實(shí)際上因?yàn)槎加蟹种嗡枷?，像是必然的?br />
那么我們查詢區(qū)間[2,3]的和，我們會(huì)這么走：
[2,3] in [1,4]->[2,2] in [1,2] & [3,3] in [3,4] -> [2,2] in [2,2] & [3,3] in [3,4]
也就是我們將這個(gè)區(qū)間按照適當(dāng)?shù)姆绞剑ò凑找延械膭澐址椒ǎ﹦澐殖?個(gè)子區(qū)間（或者正好不需要?jiǎng)澐?，繼續(xù)往下走），得到2個(gè)子區(qū)間（子問(wèn)題）的和，再加起來(lái)，得到當(dāng)前區(qū)間（大問(wèn)題）的和。我們很容易知道，這么做的時(shí)間復(fù)雜度是均攤logn的。
對(duì)半劃分子問(wèn)題的優(yōu)勢(shì)我們?cè)趯w并排序的時(shí)候已經(jīng)講過(guò)了，這里的理由類似。但是像B樹(shù)等就不是對(duì)半劃分的。
- 伸展樹(shù)
數(shù)列每次從某個(gè)點(diǎn)切割，某個(gè)點(diǎn)可以代表一個(gè)區(qū)間
- 劃分樹(shù)
數(shù)列每次按較小的一半和較大的一般切割
- 樹(shù)狀數(shù)組
和線段樹(shù)類似
- ……
一些題目
以下題目分類僅供參考。。
分治 POJ
2083
BZOJ
1095, 2001, 2229, 2287, 2458, 2229, 3614, 3658, 3879, 4025, 4059
CodeForces
321E, 576E
樹(shù)分治 POJ
1741, 1987, 2114,
BZOJ
1095, 1468, 1758, 2152, 2599, 3365, 3435, 3648, 3672, 3697, 3784, 3924, 4012, 4016, 4372
HDU
4812
CDQ分治 BZOJ
1176, 1492, 1537, 2244, 2683, 2716, 2961, 3262, 3295
總結(jié)
我們先介紹了分治法是怎么樣的一種思想，并介紹了一些典型（常見(jiàn)）的運(yùn)用了分治思想的算法和數(shù)據(jù)結(jié)構(gòu)。我們了解了分治法是如何自頂向下的。實(shí)際上現(xiàn)實(shí)生活中我們也能見(jiàn)到分治法的運(yùn)用。我們寫一個(gè)策劃，會(huì)將策劃的不同環(huán)節(jié)交給不同的人做，最后總策劃再將各個(gè)人做好的各個(gè)部分的策劃修改并整合成最終的總策劃。而每個(gè)寫子策劃的人又可能將任務(wù)繼續(xù)下派分發(fā)給部門內(nèi)部多個(gè)人員共同完成?？梢哉f(shuō)，計(jì)算機(jī)科學(xué)中的分治法源于生活。如此重要的思想，我們一定要理解。
工商網(wǎng)監(jiān)
評(píng)論