算法設(shè)計(jì)與分析王曉東

《算法設(shè)計(jì)與分析王曉東》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、習(xí)題2-1?求下列函數(shù)的漸進(jìn)表達(dá)式：3n^2+10n;?n^2/10+2n;?21+1/n;?logn^3;?10log3^n。解答：3n^2+10n=O(n^2),n^2/10+2^n=O(2^n),21+1/n=O(1),logn^3=O(logn),10log3^n=O(n).習(xí)題2-3?照漸進(jìn)階從低到高的順序排列以下表達(dá)式：n!，4n^2,logn,3^n,20n,2,n^2/3。解答：照漸進(jìn)階從高到低的順序?yàn)椋簄!、3^n、4n^2、20n、n^2/3、logn、2習(xí)題2-4(1)假設(shè)某算法在輸入規(guī)模為n時(shí)的計(jì)算時(shí)間為T

2、(n)=3*2^n。在某臺(tái)計(jì)算機(jī)上實(shí)現(xiàn)并完成該算法的時(shí)間為t秒?，F(xiàn)有另外一臺(tái)計(jì)算機(jī)，其運(yùn)行速度為第一臺(tái)計(jì)算機(jī)的64倍，那么在這臺(tái)新機(jī)器上用同一算法在t秒內(nèi)能解輸入規(guī)模為多大的問題？(2)若上述算法的計(jì)算時(shí)間改進(jìn)為T(n)=n^2，其余條件不變，則在新機(jī)器上用t秒時(shí)間能解輸入規(guī)模多大的問題？(3)若上述算法的計(jì)算時(shí)間進(jìn)一步改進(jìn)為,其余條件不變，那么在新機(jī)器上用t秒時(shí)間能解輸入規(guī)模多大的問題？解答：(1)設(shè)能解輸入規(guī)模為n1的問題，則t=3*2^n=3*2^n/64,解得n1=n+6(2)n1^2=64n^2得到n1=8n(3)由于T

3、（n)=常數(shù)，因此算法可解任意規(guī)模的問題。習(xí)題2-5??XYZ公司宣稱他們最新研制的微處理器運(yùn)行速度為其競(jìng)爭(zhēng)對(duì)手ABC公司同類產(chǎn)品的100倍。對(duì)于計(jì)算復(fù)雜性分別為n，n^2，n^3和n!的各算法，若用ABC公司的計(jì)算機(jī)能在1小時(shí)內(nèi)能解輸入規(guī)模為n的問題，那么用XYZ公司的計(jì)算機(jī)在1小時(shí)內(nèi)分別能解輸入規(guī)模為多大的問題？解答：n'=100nn'^2=100n^2得到n'=10nn'^3=100n^3得到n'=4.64nn'!=100n!得到n'

4、O(g(n))或f(n)=Ω(g(n))或f(n)=θ（g(n)），并簡(jiǎn)述理由。解答：（1）f(n)=logn^2;g(n)=logn+5.logn^2=θ（logn+5）(2)f(n)=logn^2;g(n)=根號(hào)n.logn^2=O(根號(hào)n)(3)f(n)=n;g(n)=(logn)^2.n=Ω(（logn）^2)(4)f(n)=nlogn+n;g(n)=logn.nlogn+n=Ω（logn）(5)f(n)=10;g(n)=log10.10=θ(log10)(6)f(n)=(logn)^2;g(n)=logn.(logn)^

5、2=Ω（logn）(7)f(n)=2^n;g(n)=100n^2.2^n=Ω（100n^2）(8)f(n)=2^n;g(n)=3^n.2^n=O(3^n)習(xí)題2-7證明：如果一個(gè)算法在平均情況下的計(jì)算時(shí)間復(fù)雜性為θ（f(n)），則該算法在最壞情況下所需的計(jì)算時(shí)間為Ω（f(n)）。證明：Tavg(N)=IeDn∑P(I)T(N,I)????????????≤IeDn∑P(I)IeDnmaxT(N,I')????????????=T(N,I*)IeDn∑P(I)????????????=T(N,I*)=Tmax(N)因此，Tmax(N

6、)=Ω（Tavg(N)）=Ω（θ(f(n))）=Ω（f(n)）習(xí)題2-8求解下列遞歸方程：So=0;Sn=2Sn-1+2^n-1.解答：?1應(yīng)用零化子化為齊次方程，?2解此齊次方程的特征方程，?3由特征根構(gòu)造一般解，?4再由初始條件確定待定系數(shù)，得到解為：Sn=(n-1)2^n+1習(xí)題2-9求解下列遞歸方程Ho=2;H1=8;Hn=4Hn-1-4Hn-2.解：Hn=2^(n+1)(n+1)第三章遞歸與分治策略習(xí)題3-1?下面的7個(gè)算法都是解決二分搜索問題的算法。請(qǐng)判斷這7個(gè)算法的正確性。如果算法不正確，請(qǐng)說明產(chǎn)生錯(cuò)誤的原因。如果算

7、法正確，請(qǐng)給出算法的正確性證明。publicstaticintbinarySearch1(int[]a,intx,intn){?intleft=0;intright=n-1;?while(left<=right){??intmiddle=(left+right)/2;??if(x==a[middle])returnmiddle;??if(x>a[middle])left=middle;??elseright=middle;?return-1;}publicstaticintbinarySearch2(int[]a,intx,int

8、n){?intleft=0;intright=n-1;?while(left