计算机算法分析—习题课

1、计算机算法分析计算机算法分析习题课习题课第四、五、六章第四、五、六章P99 4.2在下列情况下求解在下列情况下求解2.12.1节的递归关系式节的递归关系式 当当 g(n)=O(1) 和和 f(n)=O(n) ； g(n)=O(1) 和和 f(n)=O(1) 。 递推表达式递推表达式设n=2k则:T(n)=T(2k)=2T(2k-1)+f(2k)=22 T(2k-2)+f(2k-1) +f(2k)=22T(2k-2)+21f(2k-1)+ f(2k)=222T(2k-3)+f(2k-2)+21f(2k-1)+f(2k) =23T(2k-3)+22f(2k-2)+21f(2k-1)+f(2k)=2

2、kT(1)+2k-1f(2)+2k-2f(22)+20f(2k)=2kg(n)+ 2k-1f(2)+2k-2f(22)+20f(2k) g(n)=O(1)和和f(n)=O(n)当g(n)=O(1)和f(n)=O(n)时不妨设g(n)=a，f(n)=bn，则：T(n)=2kg(n)+ 2k-1f(2)+2k-2f(22)+20f(2k) = 2ka+ 2k-1*2b+2k-2*22b+20*2kb =2ka+kb2k =an+bnlog2n=O(nlog2n) T(n)=2kg(n)+ 2k-1f(2)+2k-2f(22)+20f(2k) g(n)=O(1)和和f(n)=O(1)当g(n)=O(

3、1)和f(n)=O(1)时，不妨设g(n)=c，f(n)=d，则：T(n)= 2kg(n)+ 2k-1f(2)+2k-2f(22)+20f(2k) =c2k+2k-1d+2k-2d+20d=c2k+d(2k-1) =(c+d) 2k-d =(c+d) n-d =O(n)P99 4.3n根据根据4.2节开始所给出的二分检索策略，写一节开始所给出的二分检索策略，写一个二分检索的递归过程。个二分检索的递归过程。Procedure BINSRCH(A, low, high, x, j)integer midif lowhigh thenmid (low+high)/2 if x=A(mid) then

4、 jmid;endifif xA(mid) then BINSRCH(A, mid+1, high, x, j);endifif xA(mid) then BINSRCH(A, low, mid-1, x, j);endifelse j0;endifend BINSRCHP99 4.5n作一个“三分”检索算法，它首先检查n/3处的元素是否等于某个x的值，然后检查2n/3处的元素。这样，或者找到x，或者把集合缩小到原来的1/3。分析次算法在各种情况下的计算复杂度。 5.三分法三分法 lowhighmid1mid2mid1=low +mid2=high -3/ )(lowhigh 3/ )(low

5、high 1(2)/ 32(2)/ 3midhighlowmidhighlowProcedure ThriSearch(A, x, n, j)integer low, high, p1, p2low1; highnwhile lowhigh dop1| (high+2low)/3 |p2| (2high+low)/3 |case:x=A(p1): jp1; return:x=A(p2): jp2; return:xA(p2): low p2+1:else: lowp1+1; highp2-1end caserepeatj0end ThriSearch实例运行实例运行 1 , 2 , 3 , 4

6、 , 5 , 6 , 7 , 8 , 9,10,11,12,13 p1| (high+2low)/3 |p2| (2high+low)/3 |E=2I+3n二元比较树二元比较树三元比较树三元比较树时间复杂度时间复杂度n成功成功:qO(1),O(log3(n), O(log3(n)q最好，最好， 平均，平均，最坏最坏n失败失败:qO(log3(n),O(log3(n), O(log3(n)q最好，最好，平均，平均，最坏最坏n注意：注意：O(log3(n)=O(log2(n) P99 4.6对于含有对于含有n个内部结点的二元树，证明个内部结点的二元树，证明E=I+2n其中，其中，E，I分别为外部和

7、内部路径长度。分别为外部和内部路径长度。证明：数学归纳法证明：数学归纳法当当n=1时，易知时，易知E=2，I=0，所以，所以E=I+2n成立；成立；假设假设nk(k0)时，时，E=I+2n成立；成立； 则当则当n=k+1时，不时，不妨认定某个内结点妨认定某个内结点x，而且它为叶结点而且它为叶结点（根据二元扩展树（根据二元扩展树的定义，一定存在的定义，一定存在这样的结点这样的结点x，且设，且设该结点的层数为该结点的层数为h），），将结点将结点x及其左右子及其左右子结点（外结点）从结点（外结点）从原树中摘除（原树中摘除（x替换替换为外结点）。为外结点）。Xk+1k此时新树内部结点为此时新树内部结点

8、为k个，则满足：个，则满足：Ek=Ik+2k（1）考察原树的外部路径长度和内部路径长度：考察原树的外部路径长度和内部路径长度：Ek+1= Ek-h+2(h+1) （2）Ik+1=Ik+h（3）综合（综合（1）（）（2）（）（3）式：）式：Ek+1= Ik+2k+h+2 = Ik+1+2k+2= Ik+1+2(k+1)故命题成立。故命题成立。P99 4.10过程MERGESORT的最坏情况时间是O(nlogn)，它的最好情况时间是什么？能说归并排序的时间是(nlogn)吗？n最好情况：最好情况：q对有序文件进行排序对有序文件进行排序n分析分析q归并的次数不会发生变化归并的次数不会发生变化 log

9、(n)次次递归树的高度递归树的高度q归并中比较的次数会发生变化（两个长归并中比较的次数会发生变化（两个长n/2序列归并）序列归并）n最坏情况最坏情况q两个序列交错大小两个序列交错大小q需要比较需要比较n-1次次n最好情况最好情况q一个序列完全大于一个序列完全大于/小于另一个序列小于另一个序列q比较比较n/2次次q差异都是线性的，不改变复杂性的阶差异都是线性的，不改变复杂性的阶n最好情况是最好情况是(nlog(n)n归并分类的时间是归并分类的时间是(nlogn)P99 4.11n写一个写一个“由底向上由底向上”的归并排序算法，从而取的归并排序算法，从而取消对栈空间的利用。消对栈空间的利用。255

10、748371292863325，5737，4812，9233，8625，37，48，5712，33，86，9212，25，33，37，48，57，86，92开 始第一次合并第二次合并第三次合并文件（25，57，48，37，12，92，86，33）算法算法Merge (R，t，m，n. X) /* 假定文件（假定文件（Rt，R t1，Rm）和文件（）和文件（R m1，Rn）都已经排序，该算法合并这两个文件后得到排序好的大文件都已经排序，该算法合并这两个文件后得到排序好的大文件（Xt，Xt1，Xn） */ M1 初始化给每个文件一个头指针初始化给每个文件一个头指针 it jml kl M2 比较比

11、较 i和和 j所指记录所指记录 WHILE（im） AND（jn） DO （IF KiKj THEN（XkRi ii1） ELSE（XkRj jjl）. kk+1）. M3 复制余留记录项复制余留记录项 WHILE (im) Xk =Ri . ii1. kk+1. WHILE (jn) Xk =Rj . jj1. kk+1. 算法算法MPass（R，n，lengthX） MP1 初始化初始化i1 MP2 合并相邻的两个长度为合并相邻的两个长度为length的子文件的子文件WHILE i n 2*length + 1 DO（Merge（R，i，ilengthl，i2*length1X）.ii2*

12、length ） MP3 处理余留的长度小于处理余留的长度小于2*length的子文件的子文件 IF i+length1 n THEN length剩余部分剩余部分2length，再合并，再合并 Merge（R，i，i+length1，n. X）ELSE 剩余部分剩余部分length，直接复制，直接复制 FOR j = i TO n DO XjRj 算法算法MSort(R，n) / 直接两路合并排序算法，直接两路合并排序算法，X是辅助文件，其记录结构与是辅助文件，其记录结构与R相同相同MS1 初始化初始化 length1 MS2 交替合并交替合并 WHILE length 0，要用的处，要用的

13、处理时间理时间ti0，限期，限期diti.n解：根据解：根据pi的非增排序得到（的非增排序得到（p7, p3, p4, p6, p2, p1, p5）=(30,20,18,6,5,3,1)，对应的期限，对应的期限为为(2,4,3,1,3,1,2)，按照算法生成的解为：，按照算法生成的解为：J=3,4,6,7顺序：顺序：6743 证明即使作业有不同的处理时间定理证明即使作业有不同的处理时间定理5.5亦真。这亦真。这里，假定作业里，假定作业I的效益的效益pi0，要用的处理时间，要用的处理时间ti0，限期限期diti.2022-5-6证明：证明： 如果如果J中的作业可以按照中的作业可以按照的次序而又

14、不违反任何一个期限的情况的次序而又不违反任何一个期限的情况来处理，则来处理，则J是一个可行解是一个可行解 若若J是一个可行解，则必存在序列是一个可行解，则必存在序列r1r2rk，使得，使得drjj, 1jk。 若若，则，则即是可行解。否则，即是可行解。否则， ，令，令a是使得是使得raia的最小下标，并设的最小下标，并设rb=ia。则有：。则有： ba 且且 dradrb (为什么为什么?) 在在中调换中调换ra与与rb，所得的新序列，所得的新序列 s1s2sk的处理次序不违反任的处理次序不违反任何一个期限。何一个期限。 重复上述过程，则可将重复上述过程，则可将转换成转换成且不违反任何一个期限

15、。故且不违反任何一个期限。故是一个是一个可行可行的调度序列的调度序列 故定理得证故定理得证。2022-5-6 i1 i2 ia ic ikr1 r2 ra rb rk ab dradrbP123-5.9n 仿照例仿照例5.4的格式，在习题的格式，在习题8所提供的数据所提供的数据集上执行算法集上执行算法5.5。nn=7(p1, p7)=(3,5,20,18,1,6,30)(d1,d7)=(1,3,4,3,2,1,2)n(p7, p3, p4, p6, p2, p1, p5)=(30,20,18,6,5,3,1)，对应的期限为对应的期限为(2,4,3,1,3,1,2)b=min n,maxd(i)

16、 =min7,4 =4F(0)F(1)F(2)F(3)F(4)01234-10-11-12-13-14F(0)F(1)F(2)F(3)F(4)01134-10-2112-13-14空空7F(0)F(1)F(2)F(3)F(4)011337,3-10-2112-2334(p7, p3, p4, p6, p2, p1, p5)=(30,20,18,6,5,3,1)，对应的期限为，对应的期限为(2,4,3,1,3,1,2)(p7, p3, p4, p6, p2, p1, p5)=(30,20,18,6,5,3,1)，对应的期限为，对应的期限为(2,4,3,1,3,1,2)F(0)F(1)F(2)F(

17、3)F(4)011137,3,4-10-41121334F(0)F(1)F(2)F(3)F(4)001137,3,4,610-511213346.3n对于标识符集（对于标识符集（a1,a2,a3,a4）=（end, goto, print, stop），已知成功检索概率为），已知成功检索概率为P(1)=1/20, P(2)=1/5, P(3)=1/10, P(4)=1/20，不成功检索概，不成功检索概率为率为Q(0)=1/5, Q(1)=1/10, Q(2)=1/5, Q(3)=1/20, Q(4)=1/20，用算法，用算法OBST对其计算对其计算W(i ,j)，R(i, j)和和C(i, j

18、)（0i, j4）。）。 P112 算法算法4.5nP（i） P(1)=1/20, P(2)=1/5, P(3)=1/10, P(4)=1/20nQ（i）Q(0)=1/5, Q(1)=1/10, Q(2)=1/5, Q(3)=1/20, Q(4)=1/20nP（i） P(1)=1, P(2)=4, P(3)=2, P(4)=1nQ（i）Q(0)=4, Q(1)=2, Q(2)=4, Q(3)=1, Q(4)=1W(i,j)=W(i,j-1)+Pj+QjWRC44+2+1=7010722+4+4=100201044+1+2=7030711+1+1=30403100WRC44+2+1=77+4+4

19、4+4=1010+2+1=13022010 2044+1+2=77+1+1=9033071211+1+1=30403100WRC44+2+1=77+4+4=1515+2+1=1818+1+1=20012220722 32 3922+4+4=1010+2+1=1313+1+1=150222010 20 2744+1+2=77+1+1=9033071211+1+1=304031006.4n证明算法证明算法OBST的计算时间是的计算时间是O(n2)。n在已知根在已知根R(i, j)，0i j4的情况下写一个的情况下写一个构造最优二分检索树构造最优二分检索树T的算法。证明这样

20、的树的算法。证明这样的树能在能在O(n)时间内构造出来。时间内构造出来。 Procedure BuildTree(m, n, R, Root)integer R(n,n), kTreeNode Root, LR, RRkR(m,n)if k0 then data(Root)k, BuileTree(m, k-1, R, LR), BuileTree(k, n, R, RR) left(Root)LR, right(Root)RRelse data(Root)m, left(Root)null, right(Root)null, endif end BuildTree时间复杂性分析：时间复杂性分析：T(n)=c+T(k)+T(n-k-1)，此递推式保证算法，此递推式保证算法的时间复杂性为的时间复杂性为O(n)，也可从递归的角度出发，递归的次数，也可从递归的角度出发，递归的次数正是结点的个数，而每次递归时间复杂性为常数，所以算法正是结点的个数，而每次递归时间复杂性为常数，所