算法分析技巧与分析习题答案

《算法分析技巧与分析习题答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、Page541.16（a）Theminimumnumberofelementcomparisonsperformedbythealgorithmisn－1.ThisminimumisachievedwhentheinputA[1..n]isalreadysortedinnondecreasingorder.（b）Themaximumnumberofelementcomparisonsperformedbythealgorithmis(n－1)+(n－2)+…+2+1=n(n－1)/2.ThismaximumisachievedwhentheinputA[1..n]isalreadysort

2、edindecreasingorder.（c）Theminimumnumberofelementassignmentsperformedbythealgorithmis0.ThisminimumisachievedwhentheinputA[1..n]isalreadysortedinnondecreasingorder.（d）Themaximumnumberofelementassignmentsperformedbythealgorithmis3[(n－1)+(n－2)+…+2+1]=3n(n－1)/2.ThismaximumisachievedwhentheinputA[1..n]i

3、salreadysortedindecreasingorder.（e）TherunningtimeofAlgorithmBUBBLESORTisO(n2)intermsoftheO-notation,andW(n)intermsoftheW-notation.（f）TherunningtimecannotbeexpressedintermsofQ-notation,becausetherunningtimerangesfromthelineartoquadratic.Page992.16（a）Ontheonehand，∑j=1njlogj≤∑j=1nnlogn≤n2logn.Ontheot

4、herhand，∑j=1njlogj≥∑j=én/2ùnén/2ùlogén/2ù≥ën/2ûén/2ùlogén/2ù≥(n-1)n/4·log(n/2).Hence，∑j=1njlogj=Q(n2logn).（b）Letf(x)=xlogx(x≥1).Sincef(x)isanincreasingfunction，wehave∑j=1njlogj≤∫1n+1xlogxdx≤(2(n+1)2ln(n+1)-(n+1)2+1)/(4ln2).Also,∑j=1njlogj=∑j=2njlogj≥∫1nxlogxdx≥(2n2lnn-n2+1)/(4ln2).Thus，有∑j=1njlogj

5、=Q(n2lnn)=Q(n2logn).2.18(a)Thecharacteristicequationisx=3.Thus,f(n)=c·3n（n≥10），wherecisdeterminedbytheinitialvalueofthesequence:f(0).Solvingtheequationf(0)=5=c,weobtainc=5.Itfollowsthatf(n)=5·3n（n≥10）.(b)Thecharacteristicequationisx=2.Thus，f(n)=c·2n（n≥10），wherecisdeterminedbytheinitialvalueofthese

6、quence:f(0).Solvingtheequationf(0)=2=c,weobtainc=2.Itfollowsthatf(n)=2n+1（n≥10）.2.19(a)Thecharacteristicequationisx2-5x+6=0,andhencex1=2andx2=3.Thus,thesolutiontotherecurrenceis于是，f(n)=c1·2n+c2·3n（n≥10）.Tofindthevaluesofc1andc2,wesolvethetwosimultaneousequations:f(0)=1=c1+c2andf(1)=0=2c1+3c2.Solvi

7、ngthetwosimultaneousequations,weobtainc1=3andc2=-2.Itfollowsthatf(n)=3·2n-2·3n（n≥10）.(b)Thecharacteristicequationisx2-4x+4=0,andhencex1=x2=2.Thus,thesolutiontotherecurrenceis于是，f(n)=c1·2n+c2·n2n（n≥10）.Tofindtheva