【正文】 2) (5,3) (4,5) (6,6) (7,7) (9,8) x (0,0) (2,1) m(3,x) x (0,0) (2,1) m(2,x) (3,2) (5,3) 42 算法改進 ?函數 m(i,j)是由函數 m(i+1,j)與函數 m(i+1,jwi)+vi作 max運算得到的。因此，函數 m(i,j)的全部跳躍點包含于函數 m(i+1， j)的跳躍點集 p[i+1]與函數 m(i+1， jwi)+vi的跳躍點集 q[i+1]的并集中。易知， (s,t)?q[i+1]當且僅當 wi?s?c且 (swi,tvi)?p[i+1]。因此，容易由 p[i+1]確定跳躍點集 q[i+1]如下q[i+1]=p[i+1]?(wi,vi)={(j+wi,m(i,j)+vi)|(j,m(i,j))?p[i+1]} ?另一方面，設 (a， b)和 (c， d)是 p[i+1]?q[i+1]中的 2個跳躍點，則當 c?a且 db時， (c， d)受控于 (a， b)，從而 (c， d)不是 p[i]中的跳躍點。除受控跳躍點外， p[i+1]?q[i+1]中的其他跳躍點均為 p[i]中的跳躍點。 ?由此可見，在遞歸地由表 p[i+1]計算表 p[i]時，可先由 p[i+1]計算出 q[i+1]，然后合并表 p[i+1]和表 q[i+1]，并清除其中的受控跳躍點得到表 p[i]。 43 典型 例子 （ 二） n=5， c=10， w={2， 2， 6， 5， 4}， v={6， 3， 5， 4， 6}。 初始時 p[6]={(0,0)}， (w5,v5)=(4,6)。因此，q[6]=p[6]?(w5,v5)={(4,6)}。 p[5]={(0,0),(4,6)}。 q[5]=p[5]?(w4,v4)={(5,4),(9,10)}。從跳躍點集 p[5]與 q[5]的并集p[5]?q[5]={(0,0),(4,6),(5,4),(9,10)}中看到跳躍點 (5,4)受控于跳躍點 (4,6)。將受控跳躍點 (5,4)清除后，得到p[4]={(0,0),(4,6),(9,10)} q[4]=p[4]?(6， 5)={(6， 5)， (10， 11)} p[3]={(0， 0)， (4， 6)， (9， 10)， (10， 11)} q[3]=p[3]?(2， 3)={(2， 3)， (6， 9)} p[2]={(0， 0)， (2， 3)， (4， 6)， (6， 9)， (9， 10)， (10， 11)} q[2]=p[2]?(2， 6)={(2， 6)， (4， 9)， (6， 12)， (8， 15)} p[1]={(0， 0)， (2， 6)， (4， 9)， (6， 12)， (8， 15)} p[1]的最后的那個跳躍點 (8,15)給出所求的最優(yōu)值為 m(1,c)=15。 44 算法復雜度分析 上述算法的主要計算量在于計算跳躍點集p[i](1≤i≤n)。由于 q[i+1]=p[i+1]?(wi， vi)，故計算q[i+1]需要 O(|p[i+1]|)計算時間。合并 p[i+1]和q[i+1]并清除受控跳躍點也需要 O(|p[i+1]|)計算時間。從跳躍點集 p[i]的定義可以看出， p[i]中的跳躍點相應于 xi,…,x n的 0/1賦值。因此， p[i]中跳躍點個數不超過 2ni+1。由此可見，算法計算跳躍點集 p[i]所花費的計算時間為 從而，改進后算法的計算時間復雜性為 O(2n)。當所給物品的重量 wi(1≤i≤n)是整數時， |p[i]|≤c+1，(1≤i≤n)。在這種情況下，改進后算法的計算時間復雜性為 O(min{nc,2n})。 ? ?nniinniOOipO 22|]1[|22?????????????? ? ?????45 最優(yōu)二叉搜索樹 ? 什么是二叉搜索樹 ？ （ 1）若它的左子樹不空，則左子樹上 所有 節(jié)點的值 均小于 它的根節(jié)點的值； （ 2）若它的右子樹不空，則右子樹上 所有 節(jié)點的值 均大于 它的根節(jié)點的值； （ 3 它的左 、 右子樹也分別為二叉排序樹 45 12 53 3 37 24 100 61 90 78 在隨機的情況下，二叉查找樹的平均查找長度 和 是等數量級的 nlog46 二叉查找樹的期望耗費 ? 查找成功與不成功的概率 ? 二查找樹的期望耗費 ? 有 個節(jié)點的二叉樹的個數為： ? 窮舉搜索法的時間復雜度為指數級 11 0??? ?? ?niniii qp???????????????????niiiTniiiTniiiTniiiTqdpkqdpkTE0101)(d e p t h)(d e p t h1)1)(d e p t h()1)(d e p t h() inco s t s e ar ch(n )/4( 2/3nn?0d 1d2d 3d4d5d1k2k3k4k5k47 二叉查找樹的期望耗費示例 2 . 8 0 T o t a l0 . 4 0 0 . 1 0 3 0 . 2 0 0 . 0 5 3 0 . 2 0 0 . 0 5 3 0 . 2 0 0 . 0 5 3 0 . 3 0 0 . 1 0 2 0 . 1 5 0 . 0 5 2 0 . 6 0 0 . 2 0 2 0 . 2 0 0 . 1 0 1 0 . 1 5 0 . 0 5 2 0 . 1 0 0 . 1 0 0 0 . 3 0 0 . 1 5 1 onc o n t r i b u t iy p r o b a b i l i t d e p t h node54321 054321ddddddkkkkk0d 1d2d 3d 4d 5d1k2k3k4k5k48 最優(yōu)二叉搜索樹 最優(yōu)二叉搜索樹 Tij的平均路長為 pij，則所求的最優(yōu)值為 p1,n。由最優(yōu)二叉搜索樹問題的最優(yōu)子結構性質可建立計算 pij的遞歸式如下 記 wi,jpi,j為 m(i,j)，則 m(1,n)=w1,np1,n=p1,n為所求的最優(yōu)值。計算 m(i,j)的遞歸式為 注意到， 可以得到 O(n2)的算法 }{m i n ,1,11,1, jkjkkikijkijijiji pwpwwpw ?????? ???niiimjijkmkimwjimjkiji????????????1,0)1,() } ,1()1,({m i n),( ,)},1()1,({m i n)},1()1,({m i n ]][1[]1][[ jkmkimjkmkim jiskjisjki ??????? ??????