上機實驗 書上 121 頁 5。 2 5。 3 書上 151 6。 1 6。 3 6。 6 他說搞懂這幾題和實驗就沒問題了 T(n)= ()2 ( / 2 ) ( )n f n否則足夠小n 當 n=2k g(n)= O(1)和 f(n)= O(n)； n=2k g(n)= O(1)和 f(n)= O(1)。 解 : T(n)=T(2k)=2 T(2f(2k)=2(2 T(2f(2 +f(2k) =22T(221 f(2 f(2k) = =2)+2)+22)+2 0f(2k) =2kg(n)+ 2)+22)+2 0f(2k) 當 g(n)= O(1)和 f(n)= O(n)時， 不妨設 g(n)=a， f(n)=a， 則 T(n)=T(2k)= 22b+22b+2 0*22ka+ =an+O( 當 g(n)= O(1)和 f(n)= O(1)時， 不妨設 g(n)=c， f(n)=d， c， 則 T(n)=T(2k)=2+2 0d=d(2=(c+d)O(n) 一個二分檢索的遞歸過程。 , x, j) if 2/)( if x=A(j if xA(, , x, j); if xA( : ; j 0 (n)= )()3/()( 否則足夠小n g(n)= O(1) f(n)= O(1) 成功 : O(1), O(n), O(n) 最好， 平均， 最壞 失敗 : O(n), O(n), O(n) 最好， 平均， 最壞 于含有 n 個內部結點的二元樹，證明 E=I+2n，其中， E， I 分別為外部和內部路徑長度。 證明：數學歸納法 當 n=1時，易知 E=2， I=0，所以 E=I+2n 成立； 假設 n k(k0)時， E=I+2 則當 n=k+1 時，不妨假 定 找到 某個內結點 x 為葉結點（根據二元擴展樹的定義，一定存在這樣的結點 x，且設該結點的層數 為 h），將結點 結點）從原樹中摘除， 生成 新二元擴展樹 。 此時新二元擴展樹內部結點為 k 個，則滿足 k+2k，考察原樹的外部路徑長度為 = +2h，內部路徑長度為 = ，所以 = k+h+1= +2k+2= +2(k+1)， 綜合 知 命題成立。 最壞情況時間是 O( 它的最好情況時間是什么 ？能說歸并分類的時間是 ( ？ 最好情況 ： 是 對有序文件進行排序 。 分析 ：在此情況下 歸并的次數不會發生變化 n)次 歸并中比較的次數會發生變化（兩個長 n/2序列歸并） 最壞情況 兩個序列交錯大小 ， 需要比較 最好情況 一個序列完全大于 /小于另一個序列 ， 比較 n/2次 差異都是線性的，不改變復雜性的階 因此 最好情況也是 平均復雜度 可以說 歸并分類的時間是 ( 由底向上 ” 的歸并分類算法，從而取消對棧空間的利用。 答： 見數據結構 算法 R， n， 1X） 初始化 i1 合并相鄰的兩個長度為 子文件 i n 2* 1 R， i， i l， i 2*1 X） . ii 2* 處理余留的長度小于 2*子文件 i+1 n j = 1 n Xj X， n， R） . * (確實能得到 12,22的正確值。 P=(22)(22) T=(12)=(22) U=(12) R=12 V=(22) S=21+ =(22)(22) +21-(12)(22) =22112222121212=R+T = 12 21=Q+S = 22 22=P+ =(22)(22)+12+(22)(12) =22112211212121 求以下情況背包問題的最優解， n=7， m=15， ）（71 ,. 10,5,15,7,6,18,3)和 ）（71 ,. 2,3,5,7,1,4,1)。 將以上數據情況的背包問題記為 I。設 )是物品按生成的解， )是一個最優解。問 )/ )是多少 ? 當物品按復 的討論。 解： 按照ip/(5p/5w， 1p / 1w ，6p/6w，3p/3w，7p/7w， 2p / 2w ， 4p / 4w ) = (6,5,9/2,3,3,5/3,1) 1,2,4,5,1,3,7),解為 (1,1,1,1,1,2/3,0) 所以最優解為：（ 1,2/3,1,0,1,1,1） )=166/3 按照 到 (6p,3p, 1p , 4p ,5p, 2p ,7p)= (18,15,10,7,6,5,3)， 對應的 (6w,3w, 1w , 4w ,5w, 2w ,7w)= (4,5,2,7,1,3,1) 解為 (1,1,1,4/7,0,0,0) 所以 )的解為（ 1,0,1,4/7,0,1,0） )=47，所以 )/ )=166/141. 按照到 (5w,7w, 1w , 2w ,6w,3w, 4w )=(1,1,2,3,4,5,7) 相應的 (5p,7p, 1p , 2p ,6p,3p, 4p )=(6,3,10,5,18,15,7) 解為 (1,1,1,1,1,4/5,0) 則 )的解為（ 1,1,4/5,0,1,1,1） )=54，所以 )/ )=83/81. 0/1背包問題）如果將 極大化 約束條件 M 或 1 1in 這種背包問題稱為 0/1背包問題。它要求物品或者整件裝入背包或者整件不裝入。求解此問題的一種貪心策略是：按ip/要正被考慮的物品能裝進的就將其裝入背包。證明這種策略不一定能得到最優解。 證明：當按照ip/如果所裝入的物品恰能裝滿背包時，易證為最優解，否則未必是最優解。 可舉例如下：設 n=3， M=6，（ 1 p , 2p , 3p） =(3,4,8)，（ 1 w , 2w , 3w）=(1,2,5)，按照ip/1p / 1w , 2p / 2w , 3p/3w） =(3,2,則其解為（ 1,1,0），而事實上最優解是 (1,0,1)，問題得證。 假定要將長為 1l ,2l , n 個程序存入一盤磁帶，程序 i 被檢索的頻率是果程序按 1i ,2i , 期望檢索時間（ ni jk ii 1 1 /)( 證明按 證明按 證明按if/最小值。 證明：只需證明結論 是正確的即可，現證明如下： 假設1, 1得到 1+ + ni j , 2j , 且其期望檢索式件是 ，我們只需證明 ，即可證明按照if/知 =1+ + ni 妨設程序交換程序到的期望檢索時間記為 - =0 顯然 也是最優解，將原來的最優解中所有這樣類似于反序對的程序互換位置，得到的解不比原來的最優解差，所以最終變換后得到的解也是最優解，而最終的解恰是程序按if/題得證。 l ,2l , T 和 2T 上，并且希望按照使最大檢索時間取最小值的方式存放，即，如果存放在 1T 和 2T 上的程序集合分別是 ，那么就希望所選擇的 使得 Ai Bi 最小值。一種得到 的貪心方法如下：開始將 都初始化為空，然后一次考慮一個程序，如果 Ai il=Ai Bi 則將當前正在考慮的那個程序分配給 A，否則分配給 B。證明無論是按 1l 2l l 2l 種方法都不能產生最優解。 證明：按照 1l 2l 例如下： 3 個程序（ a,b,c）長度分別為（ 1,2,3），根據題中的貪心算法，產生的解是 A=a,cB=b，則 Ai Bi 4，而事實上，最優解應為 3，所以得證 . 按照 1l 2l 例如下： 5 個程序（ a,b,c,d,e）長度分別為（ 10,9,8,6,4）根據題中的貪心算法，產生的解是 A=a,d,eB=b,c，則 Ai Bi 20，而事實上，最優解應為 19，所以得證。 當 n=7， ）（71 ,. 3,5,20,18,1,6,30) 和 ）（71 ,. 1,3,4,3,2,1,2)時，算法 證明即使作業有不同的處理時間定理 里，假定作業 ，要用的處理時間，限期id解： 根據 增 排 序 得 到(7p,3p, 4p ,6p, 2p , 1p ,5p)=(30,20,18,6,5,3,1) ，對應的期限為(2,4,3,1,3,1,2)，按照算法 )=7 )=7,J(2)=3 )=7,J(2)=4,J(3)=3 )=6, J(2)=7,J(3)=4,J(4)=3； 證明：顯然即使（id如果 J 中的作業可以按照 的次序而又不違反任何一個期限來處理，即對 次序中的任一個作業 k，應滿足kj 下面證明如果 J 是可行解，則使得 , 處理而又不違反任何一個期限 。 因為 必存在 =1r 2r 得對任意的有kj 們設 是按照1,設 ，那么令 br=然 ba，在 中將為然 還要證明為顯然二者之間的所有作業有由于 是可行解，所以 bk 以作業有作業可依新產生的排列 =1s 2s 續使用這種方法， 就可轉換成 且不違反任何一個期限，定理得證。 已知 (1),A(n 現要將另一存放在 A(n)的元素和 A(1:元素一起構成一個具有 n 個元素的 此寫一個計算時間為 O(算法。 在 A(1:n)中存放著一個 一個從堆頂 A(1)刪去最小元素后將其余元素調整成 求這新的堆存放在 A(1:，且算法時間為 O( 利用 所寫出的算法，寫一個對 析這個算法的計算復雜度。 解： ,n) i, j, k j n ; i n/2 i 1 iAj do k Aj; Aj Ai; Ai k j i ; i i/2 ,l,n) i, j, k x An; An Al i 1 j 2*i j j Aj+1) j j+1 xAj) i Aj; i j;j 2*i i n ,n) i, k i= n/2 1 , i, n) i=n 1 k A1; A1 Ai; Ai k , 1, 證明如果一棵樹的所有內部節點的度都為 k，則外部節點數 n 1. 證明對于滿足 n 1 的正整數 n，存在一棵具有 n 個外部節點的 k 元樹 T(在一棵 k 元樹中，每個節點的度至多為 k)。進而證明 T 中所有內部節點的度為 k. 證明： 設某棵樹內部節點的個數是 m，外部結點的個數是 n，邊的條數是 e，則有 e=m+ e=mk mk=m+ (m= n 1 利用數學歸納法。 當 n=1時，存在外部結點數目為 1的 k 元樹 T，并且 假設當 n m，且滿足 n 1 時，存在一棵具有 n 個外部結點的，且所有內部結點的度為 k； 我們將外部結點數 為 n(n m，且 n 1的最大值 )的符合上述性質的樹 結點 知新生成的樹 T 中外部結點的數目為 n+(顯然 n 為滿足 n 1，且比 樹 T 每個內結點的度為 k， 即 存在符合性質的樹。 綜合上述結果可知 ,命題 成立 。 證明如果 n 1，則在定理 面所描述的貪心規則對于所有的（ 1q , 2q , 成一棵最優的 當（ 1q , 2q , 11q ） =（ 3,7,8,9,15,16,18,20,23,25,28）時，畫出使用這一規則所得到的最優 3元歸并樹。 解： 通過數學歸納法證明： 對于 n=1，返回一棵沒有內部結點的樹且這棵樹顯然是最優的。 假定該算法對于（ 1q , 2q , 其中 m =(s+1 (0 s)，都生成一棵最優樹 . 則只需證明對于 (1q , 2q , 其中 n=(s+1)+1，也能生成最優樹即可。 不失一般性，假定 1q 2q 1q , 2q , 是 1q , 2q , ，設 T 是一棵對于（ 1q , 2q , 最優 k 元歸并樹。設 P 是距離根最遠的一個內部結點。如果 P的 q , 2q , 可以用 1q , 2q , 現在的兒子進行交換，這樣不增加 T 的帶權外部路徑長度。因此 T 也是一棵最優歸并樹中的子樹。于是在 T 中如果用其權為 q1+ + ，則所生成的樹 T 是關于 (1q + 2q + + ,一棵最優歸并樹。由歸納假設，在使用其權為 1q + 2q + + 以后，過程 化成去求取一棵關于 (1q + 2q + + ,最優歸并樹。因此 q , 2q , 最優歸并樹。 改過程 其輸出每對結點（ i,j）間的最短路徑，這個新算法的時 間和空間復雜度是多少？ n, A, i , j, k n, n), A(n, n), n, n), i 1 to n j 1 to n A(i ,j) i ,j) if i j (i, j) i, j ) j i, j) 0 k 1 to n i 1 to n j 1 to n (i,j)A(i,k)+A(k,j) (i,j) A(i,k)+A(k,j) i,j) i,k) i 1 to n j 1 to n do of i to j i ) k i, j) k 0 ,k) k k, j) 間復雜度 O(空間復雜度 O( 證明算法 計算時間是 O( 在已知根 R(i, j)， 0 i j 4 的情況下寫一個構造最優二分檢索樹 明這樣的樹能在 O(n)時間內構造出來。 解： 將 C 中元素的加法看做基本運算，則算法 時間復雜性為： 20( ( 1 , ) ( , 1 ) 1 )n n i j R i j 20( ( , ) ( , 1 ) 1 )n n i i m R i i m 2( ( 1 , ) ( 0 , 1 ) 1 )n m n R m n m O( m, n, R, (n,n),