北航計算機(jī)研究生課程-算法設(shè)計與分析-homework-1

1、一、已知下列遞推式：C(n)=1若n=1=2C（n2）n–1若n≥2請由定理1導(dǎo)出C(n)的非遞歸表達(dá)式并指出其漸進(jìn)復(fù)雜性。定理定理1：設(shè)ac為非負(fù)整數(shù)，bdx為非負(fù)常數(shù)，并對于某個非負(fù)整數(shù)k令n=ck則以下遞推式f(n)=d若n=1=af(nc)bnx若n=2的解是f(n)=bnxlogcndnx若a=cxf(n)=若a≠cxxxxaxxncabcncabcdc????????????????????log解：令F(n)=C(n)–1

2、則F(n)=0n=1F(n)=2C(n2)n–2n=2=2[F(n2)1]n–2=2F(n2)n利用定理1，其中：d=0a=2c=2b=1x=1并且a=cx所以F(n)=nlog2n所以C(n)=F(n)1=nlog2n1C(n)的漸進(jìn)復(fù)雜性是O(nlog2n)二、由于Prim算法和Kruskal算法設(shè)計思路的不同，導(dǎo)致了其對不同問題實例的效率對比關(guān)系的不同。請簡要論述：1、如何將兩種算法集成，以適應(yīng)問題的不同實例輸入；2、你如何評價這

3、一集成的意義？答：1、Prim算法基于頂點進(jìn)行搜索，所以適合頂點少邊多的情況。Kruskal從邊集合中進(jìn)行搜索，所以適合邊少的情況。根據(jù)輸入的圖中的頂點和邊的情況，邊少的選用kruskal算法，頂點少的選用prim算法2、沒有一個算法是萬能的，沒有一個算法是對所有情況都適合的。這一集成體現(xiàn)了針對具體問題選用最適合的方法，即具體問題具體分析的哲學(xué)思想。三、分析以下生成排列算法的正確性和時間效率：HeapPermute(n)實現(xiàn)生成排列的H

4、eap算法證畢。時間復(fù)雜度遞推公式為T(n)=1n=1=n[T(n1)2]n1化簡得T(n)=n!O(nn1)所以時間復(fù)雜度為O(n!)O(nn1)四、對于求n個實數(shù)構(gòu)成的數(shù)組中最小元素的位置問題，寫出你設(shè)計的具有減治思想算法的偽代碼，確定其時間效率，并與該問題的蠻力算法相比較。解：(1)(1)算法思想：將n分為[n2]，n[n2]([]表示向下取整)兩部分，分別找出其中的最小元及其位置，比較這兩個元素的大小，得出總的最小元素的位置。(

5、2)(2)偽代碼：(xi)=FindLeastElement(ab)從數(shù)組A[a…b]中找出最小元x，及其位置i輸入：全局實數(shù)數(shù)組A[1…n]，搜索起始位置a結(jié)束位置b輸出：最小元素x及其位置iififa==breturnreturn（A[a]a）elseelse(x1i)=FindLeastElement(1[n2])(x2j)=FindLeastElement([n2]1n)ififx11化簡：F(n)=2F(n2)1=2[2F(n