Solutions for Introduction to Algorithms 2nd

Solutions for Introduction to Algorithms 2nd

ID:37946697

大小:315.75 KB

页数:21页

时间:2019-06-03

Solutions for Introduction to Algorithms 2nd_第1页
Solutions for Introduction to Algorithms 2nd_第2页
Solutions for Introduction to Algorithms 2nd_第3页
Solutions for Introduction to Algorithms 2nd_第4页
Solutions for Introduction to Algorithms 2nd_第5页
资源描述:

《Solutions for Introduction to Algorithms 2nd》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、SolutionsforIntroductiontoAlgorithms2ndEdition小高子gaochangjian@gmail.com2009年12月23日2目录第一章算法在计算中的作用5第二章算法入门7第三章函数的增长9第四章递归式114.1代换法.........................................114.2递归树方法......................................114.3主方法.........................................12思考题..

2、..........................................1334第一章算法在计算中的作用56第二章算法入门78第三章函数的增长910第四章递归式4.1代换法4.2递归树方法4.2-14.2-24.2-3画出T(n)=4T(⌊n/2⌋)+cn的递归树,并给出其解的渐近确界,其中c是一个常数。然后,用代换法证明你给出的界。第i层结点的值为c(⌊n/2i⌋),i>0,最后一层为T(1),即⌊n/2i⌋=1,因此递归树一共有i=lgn层。每一层的结点个数为4i,因此每一层的总代价为4i·c(⌊n/2i⌋),其中最后一层的总

3、代价为4lgn·T(1)=Θ(4lgn)=Θ(nlg4)=Θ(n2)。于是可以得到整棵递归树的代价:lg∑n−1ii2T(n)=4·c(⌊n/2⌋)+Θ(n)i=0lg∑n−1icn264·+Θ(n)2ii=0lg∑n−1i2=cn2+Θ(n)i=02lgn−12=cn·+Θ(n)2−12=cn(n−1)+Θ(n)222=cn−cn+Θ(n)=Θ(n)(4.1)因此这棵递归树的渐近确界为Θ(n2)。现在用代换法进行证明,假设T(⌊n/2⌋)6c(⌊n/2⌋)2,则:T(n)=4T(⌊n/2⌋)+cn264c(⌊n/2⌋)+cn(n)22264

4、c+cn=cn+cn6cn(4.2)2114.3主方法4.3-1用主方法来给出下列递归式紧确的渐近界:a)T(n)=4T(n/2)+n在这个递归式中,a=4,b=2,f(n)=n,则nlogba=nlog24=n2。因为f(n)

5、(nlogba)=Θ(n2),所以满足主定理的第二种情况,因此T(n)=Θ(nlogbalgn)=Θ(n2lgn)。c)T(n)=4T(n/2)+n3在这个递归式中,a=4,b=2,f(n)=n3,则nlogba=nlog24=n2。因为f(n)>nlogba,尝试主定理的第三种情况是否成立。首先f(n)=Ω(nlogba+")=Ω(nlog24+1),其中ε=1。其次对足够大的n,要使af(n/b)6cf(n)成立,则:()n4f6cf(n)2(n)3346cn21c>(4.3)2存在常数16c<1,因此满足第三种情况,则T(n)=Θ(f(

6、n))=Θ(n3)。24.3-2某个算法A的运行时间由递归式T(n)=7T(n/2)+n2表示;另一个算法A′的运行时间为T′(n)=aT′(n/4)+n2。若要A′比A更快,那么a的最大整数值是多少?对于递归式T(n),f(n)=n2,nlogba=nlog27,且存在常数ε使得f(n)=O(nlogba−"),满足主定理的第一种情况,因此T(n)=Θ(nlog27)。对于递归式T′(n),f(n)=n2,nlogba=nlog4a。若要求出使算法A′比A快的最大整数a,必定得使递归式T′(n)满足主定理的第一种情况,因为只有第一种情况下a

7、的值才是最大的。因此T′(n)=Θ(nlog4a)。因为A′比A快,所以:Θ(nlog4a)<Θ(nlog27)nlog4a

8、)=Θ(lgn)。4.3-4主方法能否应用于递归式T(n)=4T(n/2)+n2lgn?为什么?给出此递归式的渐近上界。f(n)=n2lgn,nlogba=n2,尝

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

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

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