分治法分為三個(gè)步驟:
Divide - 將一個(gè)問題拆分成若干個(gè)子問題(規(guī)模更小)
Conquer - 通過遞歸的方法分別解決第一步中的每個(gè)子問題
Combine - 將各個(gè)子問題的結(jié)果合并起來(lái)得到整個(gè)問題的結(jié)果
典型的分治法算法
歸并排序(Merge sort之前介紹過)
T(n) = 2T(n/2) + n | 滿足主定理Case2
=》T(n) = Θ(nlgn)二分查找(Binary search)
在一個(gè)已經(jīng)排序的數(shù)組中找到x
把x于數(shù)組的中間節(jié)點(diǎn)比較,有三種結(jié)果:
1.x=middle,返回結(jié)果
2.x<middle,左半邊數(shù)組進(jìn)行遞歸查找
3.x>middle窝爪,同理右半邊數(shù)組進(jìn)行遞歸查找
T(n) = T(n/2) + Θ(1) =》 T(n) = Θ(lgn)乘方問題(Power the number
給定x,n>0,求解xn
if n是偶數(shù)衙伶,xn = xn/2 * xn/2
if n是基數(shù),xn = x(n-1)/2 * x(n-1)/2 * x
T(n) = T(n/2) + Θ(1) =》 T(n) = Θ(lgn)-
斐波那契數(shù)列
0 1 1 2 3 5 8 13 ...
樸素算法:Fn = Fn-1 + Fn-2
算法效率為Ω(φn)呼畸,指數(shù)級(jí)別的痕支,遞歸子問題的規(guī)模沒有明顯減小,并且又重復(fù)計(jì)算的部分
自底向上算法:計(jì)算 0 1 1 2 3 5... 直到Fn
避免了重復(fù)計(jì)算蛮原,算法效率提高到了Θ(n)
遞歸平方算法:
問題的求解即成為了矩陣的乘方問題卧须,算法效率于是提高到了Θ(lgn)
-
矩陣乘法nxn階矩陣
有兩個(gè)矩陣A[ij]、B[ij]儒陨,求解C=A*B
Cij=Σ(Aik * Bkj) | k <- 1 to n
樸素算法:需要三層循環(huán)(i\j\k分別從1到n循環(huán)計(jì)算花嘶,見文末補(bǔ)充),算法的效率為Θ(n3)
分治算法:將矩陣分成四個(gè)相同大小
r=ae+gb
s=af+bh
t=ce+dg
u=cf+dh
T(n) = 8T(n/2) + Θ(n2) | 分成遞歸八個(gè)乘法蹦漠,每個(gè)小問題是原來(lái)的1/2椭员,加上4次矩陣加法運(yùn)算
=> T(n) = Θ(n3) 效率并沒有提高
Strassen算法:
主定理方法可知必須想辦法將2中遞歸式中的系數(shù)8減少。Strassen提出了一種將系數(shù)減少到7(log27<3)的分治法方案
P1=a(f-h)
P2=(a+b)h
P3=(c+d)e
P4=d(g-e)
P5=(a+d)(e+h)
P6=(b-d)(g+h)
P7=(a-c)(e+f)
r=P5+P4-P2+P6
s=P1+P2
t=P3+P4
u=P5+P1-P3-P7
問題轉(zhuǎn)變成遞歸7次乘法和18次加減法
T(n) = 7T(n/2) + Θ(n2) =》 T(n) = Θ(nlg7) = Θ(n2.81)
效率提高笛园,并且因?yàn)槭侵笖?shù)級(jí)增長(zhǎng)隘击,當(dāng)n更大時(shí)提升效率明顯
~現(xiàn)在理論上矩陣乘法的效率最好的是:Θ(n^2.376…)侍芝。但是在這眾多的優(yōu)化算法中,Strassen算法卻是最簡(jiǎn)單的~
補(bǔ)充:矩陣乘法nxn階矩陣樸素算法
for i ← 1 to n
do for j ← 1 to n
do c[i][j] ← 0
for k ← 1 to n
do c[i][j] ← c[i][j] + a[i][k]? b[k][j]