- 1、本文档共12页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
算法设计习题_48290
作业
证明下列Ο、Ω和Θ的性质
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
您可能关注的文档
- 科技查新咨询工作_33443.ppt
- 科技工作者应该有严谨的治学态度和实事求是的学术作风_33446.doc
- 科技论文写作4(量和单位)_33450.ppt
- 科特勒--玩具市场细分_33470.ppt
- 科普示范市工作书册_33464.doc
- 科研中期检查_33502.doc
- 科目二场内考试计划单_33460.doc
- 科特勒关于市场塑_33469.ppt
- 秘书原理第四套作业及答案_37078.docx
- 秘书参谋职能概论概要_37073.doc
- 《GB/T 32151.42-2024温室气体排放核算与报告要求 第42部分:铜冶炼企业》.pdf
- GB/T 32151.42-2024温室气体排放核算与报告要求 第42部分:铜冶炼企业.pdf
- GB/T 38048.6-2024表面清洁器具 第6部分:家用和类似用途湿式硬地面清洁器具 性能测试方法.pdf
- 中国国家标准 GB/T 38048.6-2024表面清洁器具 第6部分:家用和类似用途湿式硬地面清洁器具 性能测试方法.pdf
- 《GB/T 38048.6-2024表面清洁器具 第6部分:家用和类似用途湿式硬地面清洁器具 性能测试方法》.pdf
- 《GB/T 18238.2-2024网络安全技术 杂凑函数 第2部分:采用分组密码的杂凑函数》.pdf
- GB/T 18238.2-2024网络安全技术 杂凑函数 第2部分:采用分组密码的杂凑函数.pdf
- 《GB/T 17215.686-2024电测量数据交换 DLMS/COSEM组件 第86部分:社区网络高速PLCISO/IEC 12139-1配置》.pdf
- GB/T 13542.4-2024电气绝缘用薄膜 第4部分:聚酯薄膜.pdf
- 《GB/T 13542.4-2024电气绝缘用薄膜 第4部分:聚酯薄膜》.pdf
文档评论(0)