算法设计与分析王晓东

算法设计与分析王晓东

ID:1610295

大小:53.00 KB

页数:14页

时间:2017-11-12

算法设计与分析王晓东_第1页
算法设计与分析王晓东_第2页
算法设计与分析王晓东_第3页
算法设计与分析王晓东_第4页
算法设计与分析王晓东_第5页
算法设计与分析王晓东_第6页
算法设计与分析王晓东_第7页
算法设计与分析王晓东_第8页
算法设计与分析王晓东_第9页
算法设计与分析王晓东_第10页
资源描述:

《算法设计与分析王晓东》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、习题2-1 求下列函数的渐进表达式: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、法在输入规模为n时的计算时间为T(n)=3*2^n。在某台计算机上实现并完成该算法的时间为t秒。现有另外一台计算机,其运行速度为第一台计算机的64倍,那么在这台新机器上用同一算法在t秒内能解输入规模为多大的问题?(2)若上述算法的计算时间改进为T(n)=n^2,其余条件不变,则在新机器上用t秒时间能解输入规模多大的问题?(3)若上述算法的计算时间进一步改进为,其余条件不变,那么在新机器上用t秒时间能解输入规模多大的问题?解答:(1)设能解输入规模为n1的问题,则t=3*2^n=3*2^n/64,解得

3、n1=n+6(2)n1^2=64n^2得到n1=8n(3)由于T(n)=常数,因此算法可解任意规模的问题。习题2-5  XYZ公司宣称他们最新研制的微处理器运行速度为其竞争对手ABC公司同类产品的100倍。对于计算复杂性分别为n,n^2,n^3和n!的各算法,若用ABC公司的计算机能在1小时内能解输入规模为n的问题,那么用XYZ公司的计算机在1小时内分别能解输入规模为多大的问题?解答:n'=100nn'^2=100n^2得到n'=10nn'^3=100n^3得到n'=4.64nn'!=100n!得到

4、n'

5、f(n)=10;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)

6、IeDnmaxT(N,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再由初始条件确定待定系数,得到解为:Sn=(n-1)2^n+1习题2-9求解下列递归方程Ho=2;H1=8;Hn=4Hn-1

7、-4Hn-2.解:Hn=2^(n+1)(n+1)第三章递归与分治策略习题3-1 下面的7个算法都是解决二分搜索问题的算法。请判断这7个算法的正确性。如果算法不正确,请说明产生错误的原因。如果算法正确,请给出算法的正确性证明。publicstaticintbinarySearch1(int[]a,intx,intn){ intleft=0;intright=n-1; while(left<=right){  intmiddle=(left+right)/2;  if(x==a[middle])retu

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

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。