計算機算法分析 習(xí)題課 第四章： 2 、 3、 5、 6、 10、 11、 23 下列情況下求解 (n)= ()2(/2) () 足夠小否則 當(dāng) g(n)=O(1)和 f(n)=O(n)； g(n)=O(1)和 f(n)=O(1)。 設(shè) n=2 T(n)=T(2k)=2T(2f(2k) =2(2 T(2f(2 +f(2k) =22T(221f(2 f(2k) = =2)+2)+22)+ +20f(2k) =2kg(n)+ 2)+22)+ +20f(2k) g(n)=O(1)和 f(n)=O(n) 當(dāng) g(n)=O(1)和 f(n)=O(n)時 不妨設(shè) g(n)=a， f(n)=： T(n)=T(2k) = 22b+22b+ +20*22ka+an+(g(n)=O(1)和 f(n)=O(1) 當(dāng) g(n)=O(1)和 f(n)=O(1)時， 不妨設(shè) g(n)=c， f(n)=d，則： T(n)=T(2k) = +20d =d(2=(c+d) (n) 根據(jù) 一個二分檢索的遞歸過程 。 , x, j) if (2 if x=A(j if xA(, , x, j); if xA( :; j 0 例運行 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 361 時間復(fù)雜度 成功 : O(1),O(n),O(n) 最好，平均，最壞 失敗 : O(n),O(n),O(n) 最好，平均，最壞 于含有 明 E=I+2n 其中， E， 證明：數(shù)學(xué)歸納法 當(dāng) n=1時，易知 E=2， I=0，所以 E=I+2 假設(shè) n k(k0)時， E=I+2 此時新樹內(nèi)部結(jié)點為 滿足： k+2k（ 1） 考察原樹的外部路徑長度和內(nèi)部路徑長度： = (h+1) （ 2） =Ik+h（ 3） 綜合（ 1）（ 2）（ 3）式： = k+h+2 = k+h+2 = +2(k+1) 故命題成立。 程 (它的最好情況時間是什么？能說歸并分類的時間是 (？ 最好情況： 對有序文件進行排序 分析 歸并的次數(shù)不會發(fā)生變化 n)次 歸并中比較的次數(shù)會發(fā)生變化（兩個長 n/2序列歸并） 最壞情況 兩個序列交錯大小 需要比較 最好情況 一個序列完全大于 /小于另一個序列 比較 n/2次 差異都是線性的，不改變復(fù)雜性的階 最好情況也是 n), 平均復(fù)雜度 n)。 寫一個 “由底向上 ”的歸并分類算法，從而取消對?？臻g的利用。 見數(shù)據(jù)結(jié)構(gòu) 238 算法 R， n， 1X） 初始化 i 1 合并相鄰的兩個長度為 i n 2* 1 R， i， i l， i 2* X） . i i 2* 處理余留的長度小于 2* IF i+ 0，要用的處理時間 ，限期 解：根據(jù) (30,20,18,6,5,3,1)，對應(yīng)的期限為 (2,4,3,1,3,1,2)，按照算法 )=7(2), )=7(2), J(2)=3(4)； )=7(2), J(2)=4(3),J(3)=3(4)； )=6(1), J(2)=7(2),J(3)=4(3),J(4)=3(4)； 證明即使作業(yè)有不同的處理時間定理 里，假定作業(yè) ，要用的處理時間 ，限期 定理 個作業(yè)的集合 , = 它使得 當(dāng)且僅當(dāng) 的次序又不違反任何一個期限的情況下來處理 . 證明：顯然即使 （ 如果 J 中的作業(yè)可以按照 的次序而又不違反任何一個期限來處理，即對 次序中的任一個作業(yè) k，應(yīng)滿足 = J 就是一個可行解。下面證明如果 J 是可行解， =得 J 中的作業(yè)可以按照 列排列而又不違反任何一個期限。 J 是可行解，則必存在 =使得對任意的 有 =們設(shè) 是按照 列的作業(yè)序列。假設(shè) ，那么令 a 是使 最小下標(biāo)，設(shè) rb=然 ba，在 中將 交換，因為 然 以按期完成作業(yè)， 我們還要證明 間的作業(yè)也能按期完成 。因為 顯然二者之間的所有作業(yè) 有 由于 是可行解，所以 1 ，所以作業(yè) 換后，仍滿足 1 ，即所有作業(yè)可依新產(chǎn)生的排列 =次序處理而不違反任何一個期限，連續(xù)使用這種方法， 就可轉(zhuǎn)換成 且不違反任何一個期限，定理得證。 對于 且僅當(dāng)子集合 果 還沒分配處理時間，則將它分配在時間片 a處理，其中 r r，且時間片 a是空的。 仿照例 習(xí)題 提供的數(shù)據(jù)集上執(zhí)行算法 易證如果 然 如果 據(jù)定理 到 ik并且按照這個順序，可以處理 對這一序列中的任意作業(yè) 果它的時間期限是 時間片 空的，則分配之；若時間片 空，則向前找最大的非空 r時間片， 1 r 是可行解，所以一定可以找到如此時間片。故命題得證。 n=7 (, =(3,5,20,18,1,6,30) (,(1,3,4,3,2,1,2) (=(30,20,18,6,5,3,1)， 對應(yīng)的期限為 (2,4,3,1,3,1,2) b=n,d(i) =,4 =4 證明如果一棵樹的所有內(nèi)部節(jié)點的度都為 k，則外部節(jié)點數(shù) 1. 證明對于滿足 n 1的正整數(shù) n，存在一棵具有 (在一棵 個節(jié)點的度至多為 k)。進而證明 k. 證明：設(shè)某棵樹內(nèi)部節(jié)點的個數(shù)是 i，外部結(jié)點的個數(shù)是 n，邊的條數(shù)是 e，則有 e=i+ik=e ik=i+ (i= n 1 證明如果 n 1，則在定理 q1,生成一棵最優(yōu)的 (當(dāng)（ q1, =（ 3,7,8,9,15,16,18,20,23,25,28）時，畫出使用這一規(guī)則所得到的最優(yōu) 3元歸并樹。 通過數(shù)學(xué)歸納法證明： 對于 n=1，返回一棵沒有內(nèi)部結(jié)點的樹且這棵樹顯然是最優(yōu)的。 假定該算法對于（ q1,，其中 m=(s+1 (s 0)，都生成一棵最優(yōu)樹， 則只需證明對于 (q1,，其中 n=(s+1)+1，也能生成最優(yōu)樹即可。 不失一般性，假定 q1,算法所找到的 是 q1,生成子樹 T，設(shè) T是一棵對于（ q1,的最優(yōu) 果 P的 q1,則可以用q1, 樣不增加 T的帶權(quán)外部路徑長度。 因此 是在 T中如果用其權(quán)為q1+一個外部結(jié)點來代換 T，則所生成的樹 T是關(guān)于(T,的一棵最優(yōu)歸并樹。由歸納假設(shè)，在使用其權(quán)為q1+那個外部結(jié)點代換了 程 T,的最優(yōu)歸并樹。因此 q1,的最優(yōu)歸并樹。 計算機算法分析 習(xí)題課 第六章 1 2 3 4 5 6 8 13 17 動態(tài)規(guī)劃 優(yōu)性原理 遞推關(guān)系式（ 右圖成立嗎？為什么？ 遞推關(guān)系式（ 什么對于含有負(fù)長度環(huán)的圖不能成立？ 解： 成立，不包含負(fù)長度環(huán) 可以使節(jié)點間的長度任意小。 修改過程 其輸出每對結(jié)點（ i,j）間的最短路徑，這個新算法的時間和空間復(fù)雜度是多少？ 回憶算法： 法 131 算法 127 算法 D(i,j)/D(j) :從節(jié)點 最優(yōu)路徑中 算法 j)的同時也計算了 D(j) 3 7行 計算出 D( j ) 之后，即可計算最短路徑。 9 11行 法 對矩陣進行初始化，每個元素賦值為邊的長 度（如果沒邊則賦值成 1 5行 迭代計算最短路徑長度 6 12行 仿照 每次計算最短路徑的時候計算出 D(j) 再通過 D(j) 就可以表示出最短路徑 k 1 to n 1 to n do j 1 to n do (i,j)A(i,k)+A(k,j) (i,j) A(i,k)+A(k,j) i,j) i,k) i 1 to n 輸出最優(yōu)路徑 j 1 to n do of i to j i ) k i, j) k 0 do k) k k, j) 析 時間復(fù)雜度 第一個循環(huán)： O(第一個循環(huán)： O(第一個循環(huán)： O(空間復(fù)雜度 n,n) A(n,n) n,n) O(對于標(biāo)識符集（ a1,a2,a3,=（ 已知成功檢索概率為 P(1)=1/20, P(2)=1/5, P(3)=1/10, P(4)=1/20，不成功檢索概率為 Q(0)=1/5, Q(1)=1/10, Q(2)=1/5, Q(3)=1/20, Q(4)=1/20，用算法(i,j)， R(i, j)和 C(i, j)（ 0 i, j 4）。 法 P（ i） P(1)=1/20, P(2)=1/5, P(3)=1/10, P(4)=1/20 Q（ i） Q(0)=1/5, Q(1)=1/10, Q(2)=1/5, Q(3)=1/20, Q(4)=1/20 P（ i） P(1)=1, P(2)=4, P(3)=2, P(4)=1 Q（ i） Q(0)=4, Q(1)=2, Q(2)=4, Q(3)=1, Q(4)=1 證明算法 ( 在已知根 R(i, j)， 0 i 1121()()() 最優(yōu)性原理并不總是對可以將其解看成是一系列決策結(jié)果的所有問題成立。找兩個最優(yōu)性原理不成立的例子，并說明對這兩個問題最優(yōu)性原理為什么不成立。 多段圖問題：路徑和改為路徑乘積并允許出現(xiàn)負(fù)數(shù) 計算機算法分析 習(xí)題課 第八章： 1、 3、 8、 9 改算法 它們只求出問題的一個解而不是問題的全部解 算法 8.1 n) n; : n) k 1 do (k)使得 X(k) T ( X(1), ,X(k k ( X(1), ,X(k) = X(1), ,X(k) ) 是一條抵達(dá)一答案節(jié)點的路徑 X(1), ,X(k) k k 1 k 1 法 8.2 k) n, X(1:n) (k) X(k) T ( X(1), ,X(k k( X(1), ,X(k)= do X(1), ,X(k) 是一條抵達(dá)一答案結(jié)點的路徑 X(1), ,X(k)