算法分析習題

計算機算法分析—習題課

第四章：2、3、5、6、10

第五章：2、3、8、9、11、12

1算法分析習題課4-22算法分析習題課4-2 當g(n)=O(1)和f(n)=O(n)時不妨設(shè)g(n)=a，f(n)=bn，則：

T(n)=2T(n/2)+bn=4T(n/4)+2bn=…=2kT(n/2k)+kbn =an+bnlog2n=O(nlog2n)

3算法分析習題課4-2當g(n)=O(1)和f(n)=O(1)時，不妨設(shè)g(n)=c，f(n)=d，則：

T(n)=2T(n/2)+d=4T(n/4)+2d =2kT(n/2k)+kd=… =cn+dlog2n=O(n)4算法分析習題課4-3根據(jù)2.2節(jié)開始所給出的二分檢索策略，寫一個二分檢索的遞歸過程。5算法分析習題課ProcedureBINSRCH(A,low,high,x,j) integermid iflow≤highthen mid←

(low+high)/2

case:x=A(mid):

j←mid;return :x>A(mid):BINSRCH(A,mid+1,high,x,j) :x<A(mid):BINSRCH(A,low,mid-1,x,j)

endcase else j←0;

endifendBINSRCH6算法分析習題課4-5作一個“三分”檢索算法，它首先檢查n/3處的元素是否等于某個x的值，然后檢查2n/3處的元素。這樣，或者找到x，或者把集合縮小到原來的1/3。分析算法在各種情況下的計算復雜度。7算法分析習題課ProcedureThriSearch(A,n,x,j) integerlow,high,p1,p2 low←1;high←n

whilelow≤highdo

p1←

(high+2low)/3

p2←

(2high+low)/3

case :x=A(p1):j←p1;return :x=A(p2):j←p2;return :x<A(p1):high←p1-1 :x>A(p2):low←p2+1 :else:low←p1+1;high←p2-1

endcase repeat j←0endThriSearch8算法分析習題課時間復雜度成功:O(1), O(log3(n)), O(log3(n))最好， 平均， 最壞失敗:O(log3(n)), O(log3(n)), O(log3(n))最好， 平均， 最壞9算法分析習題課4-6對于含有n個內(nèi)部結(jié)點的二元樹，證明E=I+2n其中，E，I分別為外部和內(nèi)部路徑長度。證明：數(shù)學歸納法當n=1時，易知E=2，I=0，所以E=I+2n成立；假設(shè)n≤k(k>0)時，E=I+2n成立；10算法分析習題課則當n=k+1時，不妨認定某個內(nèi)結(jié)點x，而且它為葉結(jié)點（一定存在這樣的x，且設(shè)該結(jié)點的層數(shù)為h），將結(jié)點x及其左右子結(jié)點（外結(jié)點）從原樹中摘除（x替換為外結(jié)點）。X新樹內(nèi)部結(jié)點為k個,滿足：

Ek=Ik+2k(1)原樹的內(nèi)、外部路徑長度：

Ek+1=Ek-h+2(h+1)(2)

Ik+1=Ik+h (3)綜合(1)(2)(3)式：

Ek+1=Ik+2k+h+2 =Ik+1-h+2k+h+2 =Ik+1+2(k+1)故命題成立。11算法分析習題課4-10過程MERGESORT的最壞情況時間是O(nlogn)，它的最好情況時間是什么？能說歸并分類的時間是Θ(nlogn)嗎？12算法分析習題課基于分治策略的算法-歸并分類ProcedureMERGESORT(low,high)iflow<highthenmid←

(low+high)/2

callMERGESORT(low,mid)callMERGESORT(mid+1,high)callMERGE(low,mid,high)

endifEndMERGESORT13算法分析習題課最好情況：對有序文件進行排序分析遞歸的次數(shù)不會發(fā)生變化----log(n)次歸并中比較的次數(shù)會發(fā)生變化（兩個長n/2序列歸并）最壞情況兩個序列交錯大小需要比較n-1次最好情況一個序列完全大于/小于另一個序列比較n/2次差異都是線性的，不改變復雜性的階最好情況時間是O(nlogn)

，平均復雜度O(nlogn)。14算法分析習題課第五章：2、3、8、

9、11、

1215算法分析習題課5-2①求以下情況背包問題的最優(yōu)解，n=7，m=15，(p1,…,p7)=(10,5,15,7,6,18,3)和(w1,…,w7)=(2,3,5,7,1,4,1)。按照pi/wi的非增序可得(p5/w5,p1/w1,p6/w6,p3/w3,p7/w7,p2/w2,p4/w4)=(6,5,9/2,3,3,5/3,1)

所以最優(yōu)解為:(1,2/3,1,0,1,1,1)

且FO(I)=166/316算法分析習題課5-2②將以上數(shù)據(jù)情況的背包問題記為I。設(shè)FG(I)是物品按pi的非增次序輸入時由GREEDY-KNAPSACK所生成的解，F(xiàn)O(I)是一個最優(yōu)解。問FO(I)/FG(I)是多少?按照Pi的非增次序輸入時，得(p6,p3,p1,p4,p5,p2,p7)=(18,15,10,7,6,5,3)，對應的(w6,w3,w1,w4,w5,w2,w7)=(4,5,2,7,1,3,1).

則FG(I)的解為(1,0,1,4/7,0,1,0),FG(I)=47

所以FO(I)/FG(I)=166/141.17算法分析習題課5-2．③當物品按wi的非降次序輸入時，重復②的討論。按照wi的非增次序輸入時，得到(w5,w7,w1,w2,w6,w3,w4)=(1,1,2,3,4,5,7)，相應的(p5,p7,p1,p2,p6,p3,p4)=(6,3,10,5,18,15,7)

則FW(I)的解為(1,1,4/5,0,1,1,1),FW(I)=54

所以FO(I)/FW(I)=83/81.18算法分析習題課5-3(0/1背包問題)如果將3.3節(jié)討論的背包問題改成這種背包問題稱為0/1背包問題。它要求物品或者整件裝入背包或者整件不裝入。求解此問題的一種貪心策略是：按pi/wi的非增次序考慮這些物品，只要正被考慮的物品能裝的進就將其裝入背包。證明這種策略不一定能得到最優(yōu)解。19算法分析習題課5-3

證明：當按照pi/wi的非增次序考慮物品存放背包時，如果所裝入的物品恰能裝滿背包時，顯然為最優(yōu)解，否則未必是最優(yōu)解.可舉例如下： 設(shè)n=3,M=6,(p1,p2,p3)=(3,4,8),(w1,w2,w3)=(1,2,5)

按照pi/wi

的非增序得到

(p1/w1,p2/w2,p3/w3)=(3,2,1.6)，則其解為(1,1,0)，而事實上最優(yōu)解是(1,0,1)。問題得證。20算法分析習題課5-8①當n=7,(p1,…,p7)=(3,5,20,18,1,6,30)和(d1,…,d7)=(1,3,4,3,2,1,2)時，算法3.5所生成的解是什么？解：①pi的非增序列(p7,p3,p4,p6,p2,p1,p5)=(30,20,18,6,5,3,1)，對應的期限為(2,4,3,1,3,1,2)，按照算法3.5生成的解為：

J(1)=7(2),J(1)=7(2),J(2)=3(4)；

J(1)=7(2),J(2)=4(3),J(3)=3(4)；

J(1)=6(1),J(2)=7(2),J(3)=4(3),J(4)=3(4)；21算法分析習題課5-8②證明即使作業(yè)有不同的處理時間定理3.5亦真。這里，假定作業(yè)i的效益pi>0，要用的處理時間ti>0，限期di≥ti.定理3.5:設(shè)J是k個作業(yè)的集合,

=i1i2…ik是J中作業(yè)的一種排序,它使得di1≤di2≤…≤dik.J是一個可行解,當且僅當J中的作業(yè)可以按照

的次序又不違反任何一個期限的情況來處理.22算法分析習題課5-8證明：顯然對于ti＞0（di≥ti），如果J中的作業(yè)可以按照

的次序而又不違反任何一個期限來處理，即對

次序中的任一個作業(yè)k，應滿足dk≥，則J就是一個可行解。下面證明如果J是可行解，

=i1i2…ik使得J中的作業(yè)可以按照di1≤di2≤…≤dik

排列而又不違反任何一個期限。23算法分析習題課5-8J是可行解，則必存在

’=r1r2…rk，使得對任意ri，都有di≥，設(shè)

是按照di1≤di2≤…≤dik排列的作業(yè)序列i1i2…ik.假設(shè)

’

，那么令a是使ra

ia的最小下標，設(shè)rb=ia，顯然b>a，在

’中將ra與rb交換，因為drb≤dra，顯然ra和rb可以按期完成.還要證明ra和rb之間的作業(yè)也能按期完成。因為drb≤dra，且對二者之間的所有作業(yè)rt，都有drb≤drt，又由于

’是可行解，所以顯然，作業(yè)ra和rb交換后，所有作業(yè)均不違反期限值。連續(xù)使用這種方法，

’就可轉(zhuǎn)換成

且不違反任何一個期限，定理得證。24算法分析習題課5-9①對于3.4節(jié)的作業(yè)排序問題證明：當且僅當子集合J中的作業(yè)可以按下述規(guī)則處理時它表示一個可行解；如果J中的作業(yè)i還沒分配處理時間，則將它分配在時間片[a-1，a]處理，其中a是使得1≤r≤di的最大整數(shù)r，且時間片[a-1，a]是空的。25算法分析習題課5-9易證如果J中的作業(yè)能按上述規(guī)則處理，顯然J是可行解；如果J是可行解，根據(jù)定理3.5可知，J中的作業(yè)根據(jù)時間期限的非降次序排列，得到i1i2…ik…in

，并且按照這個順序，可以處理J中所有作業(yè)，而對這一序列中的任意作業(yè)ik，如果它的時間期限是dk，且時間片[dk-1,dk]是空的，則分配之；若時間片[dk-1，dk]非空，則向前找最大的非空[r-1,r]時間片，1≤r≤dk因為J是可行解，所以一定可以找到此時間片。故命題得證。26算法分析習題課5-9②仿照例3.5的格式，在習題8①所提供的數(shù)據(jù)集上執(zhí)行算法3.6。n=7,(p1,…,p7)=(3,5,20,18,1,6,30),(d1,…,d7)=(1,3,4,3,2,1,2)(p7,p3,p4,p6,p2,p1,p5)=(30,20,18,6,5,3,1)，對應的期限為(2,4,3,1,3,1,2)b=min{n,max{d(i)}}=min{7,4}=427算法分析習題課F(0)F(1)F(2)F(3)F(4)01234-10-11-12-13-14F(0)F(1)F(2)F(3)F(4)01134-10-2112-13-14空{(diào)7}F(0)F(1)F(2)F(3)F(4)01133{7,3}-10-2112-2334(p7,p3,p4,p6,p2,p1,p5)=(30,20,18,6,5,3,1)，對應的期限為(2,4,3,1,3,1,2)28(p7,p3,p4,p6,p2,p1,p5)=(30,20,18,6,5,3,1)，對應的期限為(2,4,3,1,3,1,2)F(0)F(1)F(2)F(3)F(4)01113{7,3,4}-10-41121334F(0)F(1)F(2)F(3)F(4)00113{7,3,4,6}10-51121334295-11①證明如果一棵樹的所有內(nèi)結(jié)點的度都為k，則外結(jié)點數(shù)n滿足nmod(k-1)=1.證明：設(shè)某棵樹內(nèi)結(jié)點個數(shù)是i，外結(jié)點個數(shù)是n，邊的條數(shù)是e，則有

e=i+n-1

ik=e

ik=i+n-1

(k-1)i=n-1

nmod(k-1)=130算法分析習題課5-11②證明對滿足nmod(k-1)=1的正整數(shù)n，存在一棵具有n個外結(jié)點的k元樹T(在一棵k元樹中，每個結(jié)點的度至多為k)。進而證明T中所有內(nèi)結(jié)點的度為k.31算法分析習題課5-11利用數(shù)學歸納法(m表示外結(jié)點數(shù)目)。當m=k時，存在外結(jié)點數(shù)目為k的k元樹T，并且T中內(nèi)結(jié)點的度為k；m=33mod(3-1)=132算法分析習題課假設(shè)當m<n，且滿足mmod(k-1)=1時，存在一棵具有m個外部結(jié)點的k元樹T，且所有內(nèi)部結(jié)點的度為k；我們將外部結(jié)點數(shù)為m的符合上述性質(zhì)的樹T中某個外部結(jié)點用內(nèi)部結(jié)點

a替代，且結(jié)點a生出k個外部結(jié)點.…a33算法分析習題課易知新生成的樹T’中外部結(jié)點的數(shù)目為n=m-1+k=m+(k-1)，因為

mmod(k-1)=1，顯然n為滿足nmod(k-1)=1，且比m大的最小整數(shù)。樹T’每個內(nèi)結(jié)點的度為k，所以n=m+(k-1)時，存在符合上述性質(zhì)的樹。故命題得證?！璦34算法分析習題課5-12①證明如果nmod(k-1)=1，則在定理3.6后面所描述的貪心規(guī)則對于所有的(q1,q2,…,qn)生成一棵最優(yōu)的k元歸并樹。(P84)35算法分析習題課5-12通過數(shù)學歸納法證明：對于n=k，返回一棵只有一個內(nèi)部結(jié)點的樹，這棵樹顯然是最優(yōu)的。假定該算法對于(q1,q2,…,qm)，其中m=(k-1)s+1(s≥0)，生成一棵最優(yōu)樹則只需證明對于(q1,q2,…,qn)，其中n=(k-1)(s+1)+1=m+k-1，也能生成最優(yōu)樹即可36算法分析習題課不失一般性，假定q1≤q2≤…≤qn，且q1,q2,…,qk是算法所找到的k棵樹的WEIGHT信息段的值。于是q1,q2,…,qk可生成子樹T.設(shè)T’是一棵對于(q1,q2,…,qn)的最優(yōu)k元歸并樹。設(shè)P是距離根最遠的一個內(nèi)部結(jié)點。如果P的k個兒子不是q1,q