1. 將原問題分解為一組子問題匙瘪，每個(gè)子問題都與原問題類型相同菩彬，但是比原問題的規(guī)模小
2. 遞歸求解這些子問題
3. 將子問題的求解結(jié)果恰當(dāng)合并，得到原問題的解

分治算法更多地是使已經(jīng)能在多項(xiàng)式時(shí)間內(nèi)解決的問題求解得更快旨枯。

二進(jìn)制乘法

假設(shè)x和y是兩個(gè)n位二進(jìn)制整數(shù)独悴，我們將每個(gè)數(shù)都一分為二例书，每個(gè)數(shù)的左半部分和右半部分都是n/2位二進(jìn)制數(shù)：

(2^{n/2}y_L + y_R) = 2^nx_Ly_L + 2^{n/2}(x_Ly_R + x_Ry_L) + x_Ry_R)

此時(shí)，T(n) = 4T(n/2) + O(n)刻炒，時(shí)間復(fù)雜度為O(n^2)

(y_L + y_R) - x_Ly_L - x_Ry_R)

矩陣乘法

兩個(gè)nn的矩陣X和Y的乘積得到另一個(gè)nn的矩陣Z=XY

直接計(jì)算

時(shí)間復(fù)雜度= = O(n^3)?)

元素?cái)?shù)目*每個(gè)元素的計(jì)算時(shí)間

分治優(yōu)化

利用矩陣乘法能夠分塊進(jìn)行的特性



從而坟奥，

其中树瞭，
\quad P_2=(A+B)H\quad P_3=(C+D)E\quad P_4=D(G-E)\quad P_5=(A+D)(E+H)\quad P_6=(B-D)(G+H)\quad P_7=(A-C)(E+F))

算法T(n) = 7T(n/2) + O(n^2)，根據(jù)主定理可得爱谁，

遞歸樹視角：

算法的遞歸調(diào)用構(gòu)成一個(gè)樹狀結(jié)構(gòu)晒喷。在深度為k的層次上，共有

換底公式

對(duì)于二進(jìn)制乘法，通常不需要將子問題的規(guī)模降至1阻塑。對(duì)于大多數(shù)處理器而言蓝撇，16位或32位的二進(jìn)制乘法都被視為一次單獨(dú)的操作

通用模式

在解決規(guī)模為n的問題時(shí)，總是先遞歸地求解a個(gè)規(guī)模為n/b的子問題陈莽，然后再

歸并排序

將該數(shù)的序列分為兩部分耘沼，遞歸地對(duì)每一部分進(jìn)行排序，最后將兩個(gè)有序子序列進(jìn)行合并

merge

function merge(x[1...k], y[1...l])
if k=0: return y[1...l]
if l=0: return x[1...k]
if x[1] <= y[1]:
    return x[1]+merge(x[2...k],y[1...l])
else:
    return y[1]+merge(x[1...k],y[2...l])

merge()時(shí)間復(fù)雜度為O(k+l)朱盐，即線性時(shí)間
mergesort()滿足T(n) = 2T(n/2) + O(n)群嗤，根據(jù)主定理可得時(shí)間復(fù)雜度為O(nlogn)

merge()的實(shí)現(xiàn)通常面臨兩個(gè)選擇：

1. 線性附加內(nèi)存，花費(fèi)將數(shù)據(jù)拷貝到臨時(shí)數(shù)組再拷貝回來的附加工作
2. 交換位置（類似插入排序）兵琳，若y半段對(duì)應(yīng)元素較小狂秘，則面臨將x半段對(duì)應(yīng)元素至x半段末尾的元素的這一子段全體右移一位的代價(jià)

做法2可能會(huì)使歸并排序退化為插入排序，因此通常選擇線性附加內(nèi)存

function merge(x[1...k], y[1...l])
init empty z[1...k+l]
xPos, yPos, zPos -> 1

while xPos <= k && yPose <= l:
    if x[xPos] <= y[yPos]:
        z[zPos++] = x[xPos++]
    else:
        z[zPos++] = y[yPos++]:

while xPos <= k
    z[zPos++] = x[xPos++]
while yPos <= l
    z[zPos++] = y[yPos++]
    
copy temp array z back

任一時(shí)刻只需要一個(gè)臨時(shí)數(shù)組躯肌，因此該臨時(shí)數(shù)組可以僅存有一個(gè)者春，merge()使用該臨時(shí)數(shù)組的任意部分

遞歸版

function mergesort(a[1...n])
Input: An array of number a[1...n]
Output: A sorted version of this array

if n > 1:
    return merge(mergesort(a[1...n/2]),
                mergesort(a[n/2+1...n]))
else:
    return a

see implement: divide.MergeSortRecur

迭代版

可以發(fā)現(xiàn)，合并操作直到遞歸進(jìn)入到單元素?cái)?shù)組的層次時(shí)才真正開始清女，1->2->4->8...依次類推(類似自底向上)

function iterative-mergesort(a[1...n])
Input: elements a1, a2, ..., an to be sorted

Q = [] (an empty queue whose elment's type is array)
for i = 1 to n:
    inject(Q, [ai])
while |Q| > 1:
    inject(Q, merge(eject(Q), eject(Q)))
return eject(Q)

see implement: divide.MergeSortIter

擴(kuò)展

在Java的泛型排序（使用Comparator）中钱烟，進(jìn)行一次元素比較可能比較昂貴（因?yàn)楸容^可能不容易被內(nèi)嵌，從而動(dòng)態(tài)調(diào)度的開銷可能會(huì)減慢執(zhí)行的速度），但是移動(dòng)元素則是省時(shí)的（因?yàn)樗鼈兪且玫馁x值拴袭，而不是龐大對(duì)象的拷貝）读第。歸并算法使用所有流行的排序算法中最少的比較次數(shù)，因此拥刻，它就是標(biāo)準(zhǔn)Java類庫中泛型排序所使用的的算法怜瞒。

通過兩兩元素之間的比較進(jìn)行排序，必須要執(zhí)行O(nlogn)次比較操作般哼。
原因
通過兩兩元素之間的比較進(jìn)行排序的算法可以通過樹結(jié)構(gòu)來描述吴汪，樹的每個(gè)葉節(jié)點(diǎn)都標(biāo)記一個(gè)關(guān)于原輸入元素序列的排列。從樹根節(jié)點(diǎn)到樹葉節(jié)點(diǎn)的最長路徑上的比較次數(shù)為該算法時(shí)間復(fù)雜度的最差情況蒸眠。

，因此最差情況下必須要執(zhí)行O(nlogn)次比較操作黔宛，即算法復(fù)雜度為O(nlogn)

選擇S中第k小元素

普通策略

1. 排序問題：對(duì)S進(jìn)行排序近刘，返回相應(yīng)位置k的元素
2. 取S中k個(gè)最小數(shù)的問題：將S中前k個(gè)元素讀入（某數(shù)據(jù)結(jié)構(gòu)）并以遞減順序?qū)ζ溥M(jìn)行排序擒贸。接著臀晃，逐個(gè)讀入剩下的元素，若該元素大于第k個(gè)元素介劫，則忽略它徽惋；否則將其放至（某數(shù)據(jù)結(jié)構(gòu)）中正確的位置，同時(shí)將第k個(gè)元素?cái)D出座韵。當(dāng)算法終止時(shí)险绘，位于第k個(gè)位置上的元素作為答案返回

其中某數(shù)據(jù)結(jié)構(gòu)可以是數(shù)組、二叉堆誉碴、等等

分治策略

對(duì)于任意給定的數(shù)v宦棺，S中的數(shù)被分成三組：

1. 

   ，比v小的數(shù)

2. 

   黔帕，與v相等的數(shù)

3. 
   代咸，比v大的數(shù)
   搜索范圍縮小，轉(zhuǎn)而在S的三個(gè)子集中進(jìn)行：
    =\begin{cases}selection(S_L, k) & if ; k<=|S_L| \v & if ; |S_L| < k <= |S_L| + |S_V| \selection(S_R, k-|S_L|-|S_V|) & if ; k > |S_L| + |S_V| \\end{cases})

在理想情況下成黄，算法T(n) = T(n/2) + O(n)呐芥，時(shí)間復(fù)雜度為O(n)

基準(zhǔn)v的選擇see also 快速排序

分治策略的實(shí)現(xiàn)

三個(gè)子集不易實(shí)現(xiàn)奋岁。

其中基準(zhǔn)v為5思瘟，指針l左側(cè)l為比基準(zhǔn)v小的數(shù)，而指針m左側(cè)為不超過基準(zhǔn)的數(shù)闻伶。當(dāng)分割時(shí)遇到比基準(zhǔn)小的數(shù)時(shí)滨攻，需要將

和

兩個(gè)子集整體向右移動(dòng)一位，耗費(fèi)極大時(shí)間

因此，實(shí)現(xiàn)時(shí)可將上述的三組放寬為：

1. 

   光绕，不超過v的數(shù)

2. v
3. 

   更鲁，不小于v的數(shù)

顯然，該變形不改變正確性

see implement: divide.FindKMin

快速傅里葉(Fourier)變換

值表示法

多項(xiàng)式具有如下性質(zhì)

一個(gè)d次多項(xiàng)式被其在d+1個(gè)不同點(diǎn)處的取值所唯一確定
如:d=1時(shí)奇钞，即任意兩點(diǎn)確定一條直線

該性質(zhì)引出d次多項(xiàng)式的值表示法澡为。

因此，對(duì)于一個(gè)d次多項(xiàng)式
 = a_0 + a_1x^1 + a_2x^2 + ... + a_dx^d)
有如下兩種表示法（該表示法能夠唯一確定該多項(xiàng)式）：

1. 系數(shù)表示法：多項(xiàng)式的系數(shù)a_0, a_1, a_2 .... a_d
2. 值表示法：A(x_0), A(x_1), A(x_2) .... A(x_d)的值

在值表示法下景埃，對(duì)于多項(xiàng)式相乘問題媒至，只要把

和

相乘，即可得到

的值谷徙，多項(xiàng)式相乘成為線性問題

在多項(xiàng)式乘法中拒啰，只要將多項(xiàng)式的變量x換成基數(shù)2，并留意進(jìn)位完慧，即可得到二進(jìn)制乘法
多項(xiàng)式乘法的應(yīng)用：信號(hào)處理
系數(shù)表示法和值表示法可以相互轉(zhuǎn)換谋旦，系數(shù)到值的過程稱為計(jì)算，值到系數(shù)的過程稱為插值

求解多項(xiàng)式相乘（A*B=C）

• 選擇

  其中

  

  屈尼，因?yàn)橄喑撕蟮亩囗?xiàng)式有

  

  個(gè)未知數(shù)

• 計(jì)算, A(x_1), ..., A(x_{n-1}))和, B(x_1), ..., B(x_{n-1}))

• 相乘得到 = A(x_k)*B(x_k))

• 插值得到 = c_0 + c_1x + ... + c_{2d}x^{2d})

册着。

若對(duì)的選取有一定技巧，則可使計(jì)算過程之間產(chǎn)生重復(fù)步驟脾歧，從而節(jié)省算法的時(shí)間甲捏。快速

若選擇它們?yōu)檎?fù)數(shù)對(duì)鞭执，即司顿。若以

 + x(4+2x^2+10x4) = A_e(x^2) + xA_o(x^2))

則，

 = A_e(x_i^2) + x_iA_o(x_i^2))

 = A_e(x_i^2) - x_iA_o(x_i^2))

若對(duì)于正負(fù)數(shù)對(duì)的使用從遞歸頂層一直到到底層估脆，那么其運(yùn)算時(shí)間滿足

 = 2T(n/2) + O(n))

假設(shè)我們底層選擇的數(shù)選擇為1钦奋，那么遞歸頂層選擇的n個(gè)數(shù)，它們應(yīng)該是旁蔼，1的n次復(fù)根锨苏，即等式 的n個(gè)復(fù)數(shù)解。

復(fù)根的理解如下：

插值TODO

寫在最后

• 立個(gè)Flag棺聊，TODO will be done some day伞租。
• 渣代碼，且輕噴?:worried:?限佩。