算法課件動態(tài)二

1、 目錄一、最優(yōu)排序二叉樹 O(n2)一、最優(yōu)排序二叉樹給n 個關鍵碼和它們的頻率，構造讓期望比較次數(shù)最小的排序二叉樹基本分析設結點 i.j 的最優(yōu)代價為 di,j,則其中 wi,j=fi+fi+1+fj,( 如果認為根結點的代價為0,則wi,j 要減去 fk). 直接計算是 O(n3) 的設 di,j 的最優(yōu)決策為 Ki,j,下面證明Ki,j-1=Ki,j=Ki+1,j從而把時間復雜度降到 O(n2)四邊形不等式凸性 (Monge condition/quadrangle inequality)wi,j+wij=wi,j+wi,j, i=ij=j單調性 ( 區(qū)間包含格上 )w(i,j)=w(i

2、,j), i=ij=j驗證四邊形不等式只需驗證wi,j+wi+1,j+1=wi+1,j+wi,j+1移項得wi+1,j+1-wi+1,j=wi,j+1-wi,j當j 固定時記函數(shù) f(x) = wx,j+1-wx,j,則上式變?yōu)?: f(i+1)=f(i),因此f(i) 是減函數(shù) , w 為凸 ; f(i) 是增函數(shù) , w 為凹固定 i 有同樣的結論 ( 減函數(shù)時為凸 )本題中的 w本題中 , w 的凸性更好證明 :wi,j+wi+1,j+1=wi,j+(wi,j+fj+1-fi)=wi+1,j+wi,j+1兩邊是完全相等的 .或者計算f(x)=wx,j+1-wx,j=fi+1= 常數(shù)常數(shù)既

3、是增函數(shù)也是減函數(shù) ,因此本題中 , w 既為凸也為凹|”|” efghij G “efgghij *( * * ( *(*YZ b * %( * * ij g * g *(Fhij情形 1.反三角不等式i=j 時, di,j+di,j=di,j+di,jdi,j+dj,j=di,j設k 為讓 di,j 取最小值的決策 ( 有多個時取最大的一個 k, 后同 ).為若 k=j,策則k 是計算 di,j 考慮過的合法決di,j=wi,j+di,k-1+dk,j兩邊加上 dj,j,得di,j+dj,j=wi,j+di,k-1+dk,j+dj,j情形 1.反三角形不等式設k 為讓 di,j 取最小值的

4、決策 . k=j 時有di,j+dj,j=wi,j+di,k-1+dk,j+dj,j用單調性和反三角形不等式 ( 歸納假設 ),有dI,j+dj,j=wi,j+di,k-1+dk,j由于 k 是最佳決策 ,右邊恰好是 di,j,這就證明了情形 1 中 kj 時類似情形 2.非的情形ij 時,右邊保留兩項 di,j 和 di,j.設二者取最小值時的決策分別為 y 和 z,仍需分zy 兩種情況 ( 對稱 ). z=y 時y 和z 是合法決策，因此 yI, 且di,j=wi,j+di,z-1+dz,j di,j=wi,j+di,y-1+dy,j下面只考慮兩式相加并整理 ,對應項寫在一起 ,得情形 2

5、. 非的情形兩式相加并整理 ,對應項寫在一起 ,右邊 =wi,j+wi,j+di,z-1+di,y-1+dz,j+dy,j因 z=y,=紅藍色分別用四邊形不等式 ,右邊wi,j+wi,j+di,z-1+di,y-1+dz,j+dy,j按紅藍色分別組合 ,得di,j+di,j=di,j+di,jzy 時類似決策單調性進一步地 , d 的凸性可以推出決策的單調性設 ki,j 為讓 dI,j 取最小值的決策 ,明ki,j=ki,j+1=ki+1,j+1, i=j下面證即: k 在同列上都是遞增的證明 : i=j 時顯然成立 .由對稱性 ,只需證明 ki,j=ki,j+1.記dkI,j=dI,k-1+

6、dk,j+wI,j,則只需要證明對于所有的ik=k=j,有決策單調性事實上，可以證明一個更強的式子dki,j-dki,j=dki,j+1-dki,j+1 (ik=k=0)k 在i,j+1 上也更優(yōu) ( 右=0)設 k 是i,j 的最優(yōu)值，則對于它左邊的任意 k,k 在i,j 更優(yōu)可推出 k 在i,j+1 上也更優(yōu) ,因此在區(qū)間 I,j大,如下圖決策單調性欲證 dki,j-dki,j=dki,j+1-dki,j+1, 移項得dki,j+dki,j+1=dki,j+1+dki,j按定義展開 ,兩邊消去 wi,j+wi,j+1,得di,k-1+dk,j+di,k-1+dk,j+1=di,k-1+dk,j+1+di,k-1+dk,j同時消去紅色部分，得dk,j+dk,j+1=dk,j+1+dk,j這就是 k=k=jj+1 時d 的凸性算法優(yōu)化由于 k 是單調 ,計算 di,j 時決策只需從ki,j-1 枚舉到 ki+1,j 即可當 L=j-i 固定時 , d1,L+1 的決策是 k1,L 到 k2,L+1 d2,