- 1、本文档共12页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
算法设计习题,算法设计与分析复习题,计算机算法与设计习题,算法导论习题答案,简便算法练习题,算法初步练习题,四年级简便算法练习题,算法导论课后习题答案,算法与程序框图习题,算法与程序框图练习题
作业
证明下列Ο、Ω和Θ的性质
f=Ο(g)当且仅当g=Ω(f)
证明:充分性。若f=Ο(g),则必然存在常数c10和n0,使得(n(n0,有f( c1*g(n)。由于c1(0,故g(n) ( 1/ c1 *f(n),故g=Ω(f)。
必要性。同理,若g=Ω(f),则必然存在c20和n0,使得(n(n0,有g(n) ( c2 *f(n).由于c2(0,故f(n) ( 1/ c2*f(n),故f=Ο(g)。
若f=Θ(g)则g=Θ(f)
证明:若f=Θ(g),则必然存在常数c10,c20和n0,使得(n(n0,有c1*g(n) (f(n) ( c2*g(n)。由于c1(0,c2(0,f(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)。
Ο(f+g)= Ο(max(f,g)),对于Ω和Θ同样成立。
证明:设F(n)= Ο(f+g),则存在c10,和n1,使得(n(n1,有
F(n) ( c1 (f(n)+g(n))
= c1 f(n) + c1g(n)
( c1*max{f,g}+ c1*max{f,g}
=2 c1*max{f,g}
所以,F(n)= Ο(max(f,g)),即Ο(f+g)= Ο(max(f,g))
对于Ω和Θ同理证明可以成立。
log(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)
设计一个算法,求给定n个元素的第二大元素,并给出算法在最坏情况下使用的比较次数。(复杂度至多为2n-3)
算法:
Void findsecond(ElemType A[])
{
for (i=2; i=n;i++)
if (A[1]A[i])
{
temp=A[1];
A[1]=A[i];
A[i]=temp;
}
for (i=3; i=n;i++)
if (A[2]A[i])
{
temp=A[2];
A[2]=A[i];
A[i]=temp;
}
return A[2];
}
该算法使用的比较次数为:2n-3
设计一个算法,求给定n个元素的最大和最小元素。(要求算法的复杂度至多为1.5n)
算法:
void Maxmin2(A;l,r;int x;int y);
{
if (l=r) { x=A[l]; y=A[r]; return;}
if (r-l=1)
{ if (A[l]A[r]) { x=A[l]; y=A[r];}
else { x=A[r]; y=A[l];}
return;
}
else { mid=(l+r) div 2;
Maxmin2(A,l,mid,x1,y1);
Maxmin2(A,mid+1,r,x2,y2);
x=min(x1,x2); y=max(y1,y2); }
}
该算法使用的比较次数为:1.5n-2
给定多项式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)能不能对算法的性能进行提高?
解:(1)该算法最坏情况下使用的加法n次,乘法2n次
(2)改进的算法为:
float Horner(A, float x)
{
p=A[n+1];
for (j=1; j=n; j++)
p=x*p+A[n-j];
return p;
}
该算法中使用加法n次,乘法n次
第二章
1.求解下列递推关系:
1)当n≥1时,f(n)=3f(n-1);f(0)=5
解:f(n)=3f(n-1)=32f(n-2
文档评论(0)