算法設計及分析王曉東

《算法設計及分析王曉東》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在學術論文-天天文庫。

1、習題2-1?求下列函數(shù)的漸進表達式：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).習題2-3?照漸進階從低到高的順序排列以下表達式：n!，4n^2,logn,3^n,20n,2,n^2/3。解答：照漸進階從高到低的順序為：n!、3^n、4n^2、20n、n^2/3、logn、2習題2-4(1)假設某算法在

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

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

4、og100=n+6.64習題2-6對于下列各組函數(shù)f(n)和g(n)，確定f(n)=O(g(n))或f(n)=Ω(g(n))或f(n)=θ（g(n)），并簡述理由。解答：（1）f(n)=logn^2;g(n)=logn+5.logn^2=θ（logn+5）(2)f(n)=logn^2;g(n)=根號n.logn^2=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;

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

6、,I')????????????=T(N,I*)IeDn∑P(I)????????????=T(N,I*)=Tmax(N)因此，Tmax(N)=Ω（Tavg(N)）=Ω（θ(f(n))）=Ω（f(n)）習題2-8求解下列遞歸方程：So=0;Sn=2Sn-1+2^n-1.解答：?1應用零化子化為齊次方程，?2解此齊次方程的特征方程，?3由特征根構造一般解，?4再由初始條件確定待定系數(shù)，得到解為：Sn=(n-1)2^n+1習題2-9求解下列遞歸方程Ho=2;H1=8;Hn=4Hn-1-4Hn-2.解：Hn=

7、2^(n+1)(n+1)第三章遞歸與分治策略習題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==a[middle])returnmiddle;??if(

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