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

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

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)階從高到低的順序為：n!、3^n、4n^2、20n、n^2/3、logn、2習(xí)題2-4(1)假設(shè)

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

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

4、00n!得到n'

5、logn）(5)f(n)=10;g(n)=log10.10=θ(log10)(6)f(n)=(logn)^2;g(n)=logn.(logn)^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證明：如果一個算法在平均情況下的計算時間復(fù)雜性為θ（f(n)），則該算法在最壞情況下所需的計算時間為Ω（f(n)）。證明：Tavg(N)=IeDn∑P(I)T(N,I)????????????

6、≤IeDn∑P(I)IeDnmaxT(N,I')????????????=T(N,I*)IeDn∑P(I)????????????=T(N,I*)=Tmax(N)因此，Tmax(N)=Ω（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;H

7、1=8;Hn=4Hn-1-4Hn-2.解：Hn=2^(n+1)(n+1)第三章遞歸與分治策略習(xí)題3-1?下面的7個算法都是解決二分搜索問題的算法。請判斷這7個算法的正確性。如果算法不正確，請說明產(chǎn)生錯誤的原因。如果算法正確，請給出算法的正確性證明。publicstaticintbinarySearch1(int[]a,intx,intn){?intleft=0;intright=n-1;?while(left<=right){??intmiddle=(left+right)/2;??if(x==

8、a[middle])returnmiddle;??if(x>a[middle])left=middle;??elseright=middle;?return-1;}publicstaticintbinarySearch2(int[]a,intx,intn){?intleft=0;intright=n-1;?while(left