算法设计习题

《算法设计习题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章作业1.证明下列Ο、Ω和Θ的性质1）f=Ο(g)当且仅当g=Ω(f)证明：充分性。若f=Ο(g)，则必然存在常数c1>0和n0，使得"n³n0，有f£c1*g(n)。由于c1¹0，故g(n)³1/c1*f(n)，故g=Ω(f)。必要性。同理，若g=Ω(f)，则必然存在c2>0和n0，使得"n³n0，有g(n)³c2*f(n).由于c2¹0，故f(n)£1/c2*f(n)，故f=Ο(g)。2）若f=Θ(g)则g=Θ(f)证明：若f=Θ(g)，则必然存在常数c1>0，c2>0和n0，使得"n³n0，有c1*g(n)£f(n)£c2*g(n)。由于c1¹0，c2¹0，f(

2、n)³c1*g(n)可得g(n)£1/c1*f(n)，同时，f(n)£c2*g(n)，有g(n)³1/c2*f(n)，即1/c2*f(n)£g(n)£1/c1*f(n)，故g=Θ(f)。3）Ο(f+g)=Ο(max(f,g))，对于Ω和Θ同样成立。证明：设F(n)=Ο(f+g)，则存在c1>0，和n1，使得"n³n1，有F(n)£c1(f(n)+g(n))=c1f(n)+c1g(n)£c1*max{f,g}+c1*max{f,g}=2c1*max{f,g}所以，F(n)=Ο(max(f,g))，即Ο(f+g)=Ο(max(f,g))对于Ω和Θ同理证明可以成立。4）log(

3、n!)=Θ(nlogn)证明：·由于log(n!)=£=nlogn，所以可得log(n!)=Ο(nlogn)。·由于对所有的偶数n有，log(n!)=³³³(n/2)log(n/2)=(nlogn)/2-n/2。当n³4，(nlogn)/2-n/2³(nlogn)/4，故可得"n³4，log(n!)³(nlogn)/4，即log(n!)=Ω(nlogn)。综合以上两点可得log(n!)=Θ(nlogn)2.设计一个算法，求给定n个元素的第二大元素，并给出算法在最坏情况下使用的比较次数。（复杂度至多为2n-3）算法：Voidfindsecond(ElemTypeA[]){f

4、or(i=2;i<=n;i++)if(A[1]

5、y=A[r];}else{x=A[r];y=A[l];}return;}else{mid=(l+r)div2;Maxmin2(A,l,mid,x1,y1);Maxmin2(A,mid+1,r,x2,y2);x=min(x1,x2);y=max(y1,y2);}}该算法使用的比较次数为：1.5n-22.给定多项式p(x)=anxn+an-1xn-1+…+a1x+a0，假设使用以下方法求解：p=a0;xpower=1;for(i=1;i<=n;i++){xpower=x*xpower;p=p+ai*xpower;}求（1）该算法最坏情况下使用的加法和乘法分别为多少次？（2）能

6、不能对算法的性能进行提高？解：（1）该算法最坏情况下使用的加法n次，乘法2n次（2）改进的算法为：floatHorner(A,floatx){p=A[n+1];for(j=1;j<=n;j++)p=x*p+A[n-j];12returnp;}该算法中使用加法n次，乘法n次第二章1．求解下列递推关系：1）当n≥1时，f(n)=3f(n-1)；f(0)=5解：f(n)=3f(n-1)=32f(n-2)=…=3nf(n-n)=3n*5=5*3n2)当n≥2时，f(n)=5f(n-1)-6f(n-2)；f(0)=1；f(1)=0解：该递推关系的特征方程为：x2-5x+6=0特征根

7、为：r1=2；r2=3故f(n)=c1*2n+c2*3n有f(0)=c1*20+c2*30==c1+c2=1且f(1)=c1*21+c2*31==2c1+c32=0可得c1=3，c2=-2故f(n)=3*2n-2*3n3)当n≥1时，f(n)=f(n-1)+n2；f(0)=0解：f(n)=f(n-1)+n2=f(n-2)+(n-1)2+n2=….=f(0)+12+22+…+(n-1)2+n2=12+22+…+(n-1)2+n2=1/6n(n+1)(2n+1)4)当n≥1时，f(n)=2f(n-1)+n2；f(0)=1解：设f(