哈工大算法设计与分析（骆吉洲）课后习题答案

【实例简介】
哈工大算法设计与分析（骆吉洲）课后习题答案，包含大部分老师留的课后思考题
(c)该算法在第5行执行比较操作,第1、3、4、7、8、9行执行赋值操 作 最坏情况下:输入数组反向排序时导致最坏情况,必须将每个元素A与 整个已排序子数组A[1:t-1]中的每个元素进行比较 算法第5行执行的比较次数为:∑2=如+2n=1 算法执行的赋值次数为:第1行为n,第3行为n-1,第4行n1,第7行为 2,第8行为∑z2(-1) n(n-1) 第9行为n 因此算法总的赋值次数为72+3n-3 最好情况下:输入数组匚经排好序时导致最好的情況,无需移动:算法 执行的比较次数为n-1:赋值次数为m+(n-1)+(n-1)+(m-1)=4n-3。 平均情况下: (a)比较次数:假设插入第k个元素吋,其插入的位置为j,1≤j≤k。则 需要比较k-j+1次,所以其平均比较次数为 ∑ k(k+1 k+ (h-j+1)=k2 +k 插入n个元素时,算法总平均比较次数为: ∑( h+1-1(2+1)n+2) 3 2 4n+4m+1 (b)赋值次数:假设插入第k个元素时,其插入位置为j1≤j≤k,第7 行执行的赋值次数为k,因此平均赋值次数为 ∑(k-j) k(k+1)1k-1 因此,插入n个元素吋,第7行总的赋值次数为: k:-1 7(n-1)1_1 则算法总的赋值次数为: 2+(m-1)+ 1)+ n)+(n-1)=2n2+方n-3 4.结合你曾进行过的程序设计过程或算法设计过程,说明算法基本技术、基本 算法和问题特征分析三者问的关系。 解 对于一个计算问题的解决,我们可以通过采用算法的基本技术对问题进行分 析求解,不同的技术分析方法不同,要分析问题可计算否,能行可计算否 然后根据分析的结果,釆用基本的算法用计算机语言进行算法实现,最终解 决这个计算问题。 第二章 1.证明:O(f(m)+O(9(m)=(f(n)+g(m) 解 由已知条件可得: 存在正常量c1,c2,m1,使得n>m1,有0≤c1f(mn)<θ(f(m)≤c2f(n) 存在正常量c3,c4,m,使得n≥m2,有0≤c39(n)≤O(g(m)≤c9(m) 取5=min(c1,),c6=max(c2,c4),m23=max(m1,m2)出上面的式子可得: 存在cs,c6,m3,使得m≥n3,有0≤csf(m)≤af(n)≤O(f(n)≤cf(m)≤ C6f(n2)。 存在G,c,m3,使得m≥n3,有0≤c59(m)≤c9(m)≤6(g(m)≤C49(m)≤ sg(n) 所以,存在c,c6,n3,使得n≥n3,有0≤Gf(m)+Cg(n)≤O(f(m)+ (m)≤c6f(m)+c69(mn) 综上所述:O(f(n)+(9(mn)=O(f(n)+g(m) 2.证明:/(m)=O(9(m)分9(m)=!((m) 解 当∫(m)=O⑨g(m)时,得到存在正常量a1,m1,使得n≥n1,有0≤∫(m)≤ C19 取 则存在正常量c,m1,使得n≥m1,有0≤c2/(n)≤g(m)。就 可以得到g(n)=9(f(m) 当g(m)=92(f(m)时,得到存在正常量a,m1,使得n≥m1,有0≤ 取②2=,则存在正常量e,n1,使得n≥m1,有0≤f(m)≤c29(m)。就 可以得到∫(m)=O(9(m) 3.证明课件中列出的复杂性函数阶的各种性质(传递性、自反性、反对称性) 解 传递性:f(n)=6((n)∧g(m)=(h(m)→f(m)=6(h(7n) 由已知得:存在正常量a1,c,m1,使得m≥m1,有0≤c19(n)≤f(m)≤ 29(m) 存在正常量3,c,m,使得n≥m,有0≤3h(m)≤9(m)≤c4h(m)。 我们取c=c1×73,c=c2XC4,m3=max(m1,m2) 由上面的式子可得:存在c,6,m3,使得m≥m3,0≤c1×c3h(mn)≤c1g(m)≤ f(m)≤c29()≤c2Xc1l(n) 就可以得到:f(m)=b(h(n),传递性得计。 自反性:f()=θ((7) 容易找到正常量a1=1,c2=1,m1=1,使得n≥m1时,有0≤c1f(m)≤ ∫(n)≤c2/(n) 所以可以得到∫(m)=((m) 反对称性:f(m)-O(9(m)9(m)-9(f(n) 我们先证明f(n)-O(9(n)→g(n)-92(f(mn) 出已知得:存在正常量a1,n1,使得n≥m1,有0≤f(n)≤c19(m)。 我们取②2-a,则存在正常量e,m,使得n>m1,有0<e2f(m)≤g(m) 就可以得到g(m)=g(f(m) 接下来我们来证明9(mn)=92(f(n)→f(m)=O(9(m) 由已知得:存在常量c1,n1,使得m≥m1,有0≤cf(m)≤g(m) 我们取②2=4,则存在正常量e2,m1,使得m≥m1,有0≤f(m)≤e2g(m 就可以得到f(n)-O(g(n) 4.证明:对任意正整数常数k,log(n)=o(n) 解 我们先给出原问题的一个等价命题:对任意正整数常数k,limn+x2=0 如果该命题成立,则可以得到vc>0,3mo>0使得n>m0时,x(n-0<c 成立。由这个可以得到log"(m)<cm,即log(n)=o(m) 利用洛比达法则,对分子分母同时求导,limn→sg"(m)-limn→g(n 连续利用洛比达法则k次,可以得到 lim log (n=limn→=0,命题 得证。 所以原命题log(n)=o(m)成立。 5.证明:logn!- o(n log n) 解 我们先证明logn!=O( nlog n) gn!-∑lg≤∑ogn- n logn=O( n logn) 再来证明logm!-9( m log n) gn!=∑ogt∑logn>∑log log . 0g log 2 n/2 2 ≥4时,当logn-2g2>×mlgm恒成立 所以logn!=9( n log n)成立。 综上所述,logm!= (nlog n) 6.对于任意实数r>1,令H(m)=+2++…+。证明:H(m)=(1) 解 我们先来证明H1(n)=92(1)。 显然,H(m) 所以H(n)=92(1)成立 接下来证明x(n)-O(1 H(n)-1+2++…+n-1+∑2=2≤1+1dx=1+ 1=r|n 1 1- 又因为r>1→1-r<0并且n>2,所以m1--1<0 所以可以得到l1(m)≤1,所以I1(n)-O( 综上所述,Hr(m)=(1),命题得证 7.证明:「og(m+1)=ogm+1对任意正整数n成立 解 设 Llog n=k≥0 则k≤gn<k+1→2≤n<2k+1 又因为n是一个正整数,则2k<n<2k+1-1 可以得到24+1≤n+1≤2+1→log(2+1)≤log(m+1)≤log(2k+1)。 又因为log(2+1)>log2k=k 所以可以得到k<log(n+1)≤log(2+)=k+1 所以「og(n+1)1=k+1=lgn」+1,命题得证。 8.证明:对于任意正整数a,b均有 a+(b-1) b/≥a-(-1) (b)「6 b 解: 这题觉得是老师出错了,上:整和下整写反了) 名」≤号≤号+-“+b,命题(a)得证。 1≥号≥-1=“b1,命题(b)得证。 现在来证一下新的命题 b-1 b时 1<1+ a+(b-1) b 1≤b≤a时,设a=b×k+r,其中k,r为整数并且k>0,0≤r≤b 所以「1=k+「石1。 当7=0时,「#1=k≤k+b1=++b1=2+b1。 ≠0时 k+1<k+1+ bxk+b+r-1 综上所述,命题(a)得证 当1≤a<b时,L名」=0≥0 当1≤b≤a时,设a=b×k+r,其中k,r为整数并且k>0,0≤r≤b 所以L」=k+L刮」。 =k>k-1 b×k-(b-1)+ra-(b-1 综上所述,命题(3)得证。 9.用迭代法解递归方程r(m)=2T(n/2)+ n log n,T(1)=1 解 6 T(n)=2T(m/2)+nlog n 2T(n/4)+2×loga+mlog n 2T(m/8)+4×log +2×logx+log (1)-2 g +…+7lo (1)∑ 上式中,k表示的是代的次数,易知k-log2n,代入上式中可得: ()=2"7(1)+∑2x log n 1 1+ ∑mlog n+n g loyo nu 2+n1 7+7 (l +72 g nH 72+2× X n 2 g2××logn+a× n log n+ O(log2n×"×logn) 10.求解下列递归方程。 (1)T(m)=5T(/3)+m,T(1) (2)T()-47(m/2)+m,T(1) (3)(m)-2(m/2)+m12,T(m)-1对n<4成立; (4)T(m)=T(m/2」)+T(3/4」)+m,T(m)=4对m<4成立; (5)T(m)-2(n/2)+n2,T(1)-1 (6)T(m)-T(n/2)+m1/2,T(m)-2对n<4成 解 (1)等式符合 master定理,其屮a-5,b-3,f(n)-m。 并且存在某个常数ε>0有n=O(ng5-) 用 master定理可得:T(n)-O(ng35 并且存在某个常数c>0有m-/b-2,f(n)=ne (2)等式符合 master定理,其中a 用 master定理可得:T(n)=(nlog4)=6(m2) (3)等式符合 master 定理,其中a=2,b=2,f(n)=m12 并且存在某个常数c>0有n2=O(n2-) 用 master定理可得:r(n)-O(ng2)-(m) (4)用迭代法估计T(n)的上:界,再用代入法验证。 T(n)=T(m/2」+T(3/4」)+m (n/4)+7(13n/8」)+T(3n/8)+r(9m/16)+m+ T(n/8」)+37(3/16)+3(9/32)-7(27n/6442+n+n 由上式可以看出当进行到第i次迭代,会增加一项()n 而对于迭代次数而言,最长的迭代路径为m→→(2)2n→…→1,所以 最大的i为 而当进行到第log2m次迭代的时候,增加的项就不足()m,会逐渐减小。 所以代价和要小于n+n∑(万y=n+57n(m0 并且代价和要大于n+n∑(y=n+5n(k-1) 所以我们猜测T(m)的上界为O(n2)。 7(m)=T(m/2」)+T(3m/4」)+m X+Cx 16 13n 只要c如2>n→c>就能成立,而n为正整数,所以c只要取大于1 的数就行 由上面可得:T(m)-O(m2) (5)等式符合 master定理,其中a=2,b=2,f(m)=m2。 并且存在某个常数e>0有n2-92(mg2+)。 用 master定理可得:T(n)-O(n2)。 (6)等式符合 master定理,其中a-1,b-2,f(m)-m1/2 并且存在某个常数c>0有m12=92(mg1+)。 用 master定理可得:T(m)-O(m212)。 9 第三章 1.根据表达式a26=a·a和a2h1=a,ab·a设计分治(或递归)算法求解下 列问题,并分析算法的时间复杂度 a)输入实数a和自然数n,输出实数a (b)输入实数矩阵A和自然数n,输出实数矩阵A" 解 a)对于这个问题,采取分治算法将原问题分解为两个规模相同的子问题进 行求解,算法设计如下 CALCULATE-POWeR(a, n) 1 if n then return a 3ifn%2==0 4 then C= CALCULAtE-POWER(a, n/ 2) return c×c else C= CALCULATE-POWER(a, nal return c×c×a 算法分析:我们可以列出算法的递归表达式 T(m)=T(Ln/2)+O(1) 出 master主定理可以很容易得到解:T(n)=(ogn) (b)我们可以采用相同的方法来分析这个问题,只是在分治算法的 merge步 骤的时候会不同。 CALCULATE-MATPOWER(A, n) f then return a ifn%2==0 then C= CALCULATE-POWER(A, n/ 2) return MATRIX-MULT(C, c) 6 else C= CALCULATE-POWER(A, 2 m=MATRIX-MULT(C, c) return MATRIX-MULT(m, A 其中, MATRIX-MULr(c,c)这个函数表示两个矩阵相乘,由题目可知,问题 中的矩阵都是方阵,设输入的矩阵A为m×m的矩阵,我们可以列出递归 表达式: T(m)=T(m/2)+ 采用迭代法求解上面的递归表达式可得:T(n)-O(m3×logn)。 【实例截图】
【核心代码】