Solutions for Introduction to Algorithms 2nd

《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，尝