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

1、一、已知下列遞推式：C(n)=1若n=1=2C（n2）n–1若n≥2請(qǐng)由定理1導(dǎo)出C(n)的非遞歸表達(dá)式并指出其漸進(jìn)復(fù)雜性。定理定理1：設(shè)ac為非負(fù)整數(shù)，bdx為非負(fù)常數(shù)，并對(duì)于某個(gè)非負(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è)計(jì)思路的不同，導(dǎo)致了其對(duì)不同問(wèn)題實(shí)例的效率對(duì)比關(guān)系的不同。請(qǐng)簡(jiǎn)要論述：1、如何將兩種算法集成，以適應(yīng)問(wèn)題的不同實(shí)例輸入；2、你如何評(píng)價(jià)這

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

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

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