算法設(shè)計與分析-homework

1、一、已知下列遞推式：C(n) = 1若n =1= 2C（n/2） + n 1 若n 2請由定理1 導(dǎo)出C(n)的非遞歸表達式并指出其漸進復(fù)雜性。定理1：設(shè)a,c為非負整數(shù)，b,d,x為非負常數(shù)，并對于某個非負整數(shù)k, 令n=ck, 則以下遞推式f(n)=d若 n=1=af(n/c)+bnx若 n=2的解是f(n)= bnxlogcn + dnx若 a=cxf(n)= 若 acx解：取f(n) = C(n) 1,則 f(n) = 0 f(n) = 2C( n / 2) + n 2 若n=1 = 2f(n / 2) + n 若n= 2帶入定理1：a = 2, d = 0, c = 2, b = 1

2、, x = 1,因為a=cx所以f(n) = nlog2n所以C(n) = f(n) + 1 = nlog2n + 1C(n)的漸進復(fù)雜度為O（nlog2n）二、由于Prim算法和Kruskal 算法設(shè)計思路的不同，導(dǎo)致了其對不同問題實例的效率對比關(guān)系的不同。請簡要論述：1、如何將兩種算法集成，以適應(yīng)問題的不同實例輸入；2、你如何評價這一集成的意義？解：Prime的時間復(fù)雜度為O(n2) （其中n 為頂點數(shù)）， Kruskal 算法的時間復(fù)雜度為 O(eln(e) （其中e為邊數(shù)），因此對于頂點少的輸入，適合Prime算法，對于邊比較少的輸入，適合Kruskal 算法。評價算法的優(yōu)劣需要根據(jù)輸

3、入數(shù)據(jù)的特點。對于不同特征的輸入最適用的算法可能不同。三、分析以下生成排列算法的正確性和時間效率：HeapPermute(n)/實現(xiàn)生成排列的Heap算法/輸入：一個正正整數(shù)n和一個全局數(shù)組A1.n/輸出：A中元素的全排列if n = 1write Aelsefor i 1 to n doHeapPermute(n-1)if n is oddswap A1and Anelse swap Aiand An解：正確性：n=1時，輸出A1n=2時，輸出A1A2，A2A1n=3時，i=1時，HeapPermute(2)輸出A1A2的全排列，并將A變?yōu)锳2A1A3，并交換1,3位，得A3A1A2i=2時

4、，HeapPermute(2)輸出A3A1的全排列，并將A變?yōu)锳1A3A2，交換1,3位，得A2A3A1i=3時，HeapPermute(2)輸出A2A3的全排列，并將A變?yōu)锳3A2A1，交換1,3位，得A1A2A3算法運行結(jié)束后，A的元素順序不變。n=4時，i=1時，HeapPermute(3)輸出A1A2A3的全排列，并且A1A2A3順序不變，交換1,4位，得A4A2A3A1i=2時，HeapPermute(3)輸出A4A2A3的全排列，并且A4A2A3順序不變，交換2,4位，得A4A1A3A2i=3時，HeapPermute(3)輸出A4A1A3的全排列，并且A4A1A3順序不變，交換3

5、,4位，得A4A1A2A3i=4時，HeapPermute(3)輸出A4A1A2的全排列，并且A4A1A2順序不變，交換4,4位，得A4A1A2A3算法運行結(jié)束后，數(shù)組A循環(huán)右移一位。因此可得出結(jié)論：當n為偶數(shù)時，HeapPermute(n)輸出全排列后數(shù)組元素循環(huán)右移一位。當n為奇數(shù)時，HeapPermute(n)輸出全排列后數(shù)組元素順序保持不變。歸納法證明如下：(1)i=1時，顯然成立。(2)i=k為偶數(shù)時，假設(shè)輸出的是全排列，則i=k+1(奇數(shù))時，k+1次循環(huán)中，每次前k個元素做全排列輸出后循環(huán)右移一位，所以對換swap A1and An可以保證每次將前k個元素中的一個換到k+1的位置

6、，所以k+1次循環(huán)后輸出的是A1k+1的全排列。(3)i=k為奇數(shù)時，假設(shè)輸出的是全排列,則i=k+1(偶數(shù))時，k+1次循環(huán)中，每次前k個元素做全排列輸出后順序保持不變，所以對換swap Aiand An可以保證每次將前k個元素中的一個換到k+1的位置，所以k+1次循環(huán)后輸出的是A1k+1的全排列。正確性得證。時間復(fù)雜度：由算法流程得：F(n) = 1 n=1= n * (F(n - 1) + 2) n1= n * (n - 1) * (F(n - 2) + 2) + 2) = n(n - 1) * F(n-2) + 2n2= n! + 2 * nn-1因此時間復(fù)雜度為O(n!) + O(n

7、n-1)四、對于求n 個實數(shù)構(gòu)成的數(shù)組中最小元素的位置問題，寫出你設(shè)計的具有減治思想算法的偽代碼，確定其時間效率，并與該問題的蠻力算法相比較。Min(A1.n, n, &loc)If(n = 1)Return A1Elseloc1, loc2Min1 = Min(A1.n/2, n/2, &loc1)Min2 = Min(An/2 + 1. n, n/2, &loc2)If(Min1 1= 2(2F(n/4) + 1) + 1 = 4F(n/4) + 2 + 1= 2kF(2k/2k) + 1 + 2 + + 2k-1 ( n=2k)= 2n 1復(fù)雜度為O（n），蠻力法也為O（n）五、請給出約瑟夫斯問題的非遞推公式 J（n），并證明之。其中，n 為最初總?cè)藬?shù)，J(n) 為最后幸存者的最初編號。 解：非遞推公式為：設(shè)J(n) = 2*b+1，其中n = 2m + b (0b1時，分兩種情況討論：當n=2k，即為偶數(shù)時，假設(shè)k = n/2時成立，即k = 2m + b，則J(k) = 2b+1，由n=2k得n = 2m+1 + 2bJ(n) = J(2k) = 2J(k) 1 = 2(2b+1) 1 = 4b + 1 = 2(2b) + 1，對n成立當n=2k+1，即為奇數(shù)時，假設(shè)k = (n-