算法课件动态二

1、 目录一、最优排序二叉树 O(n2)一、最优排序二叉树给n 个关键码和它们的频率，构造让期望比较次数最小的排序二叉树基本分析设结点 i.j 的最优代价为 di,j,则其中 wi,j=fi+fi+1+fj,( 如果认为根结点的代价为0,则wi,j 要减去 fk). 直接计算是 O(n3) 的设 di,j 的最优决策为 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单调性 ( 区间包含格上 )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 固定时记函数 f(x) = wx,j+1-wx,j,则上式变为 : f(i+1)=f(i),因此f(i) 是减函数 , w 为凸 ; f(i) 是增函数 , w 为凹固定 i 有同样的结论 ( 减函数时为凸 )本题中的 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= 常数常数既

3、是增函数也是减函数 ,因此本题中 , 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 上也更优 ( 右=0)设 k 是i,j 的最优值，则对于它左边的任意 k,k 在i,j 更优可推出 k 在i,j+1 上也更优 ,因此在区间 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 的凸性算法优化由于 k 是单调 ,计算 di,j 时决策只需从ki,j-1 枚举到 ki+1,j 即可当 L=j-i 固定时 , d1,L+1 的决策是 k1,L 到 k2,L+1 d2,