Problem 1 (教材 4.3 节习题节选)
使用代入法证明 T(n)=4T(n/3)+n 的解为 T(n)=Θ(nlog34) 。(提示:需要在假设中减去一个低阶项以完成归纳)
利用换元法求解递归式 T(n)=3T(n)+logn 。你的解应该是渐近紧确的,不必担心数值是否是整数。
Solution
- 先证上界。假设 T(m)≤cmlog34−dm 对 m<n 成立,则
T(n)≤4(c(3n)log34−d3n)+n=cnlog34−(34d−1)n≤cnlog34−dn
其中,最后一步在 d≥3 时成立。于是 T(n)=O(nlog34) 。
再证下界。假设 T(m)≥cmlog34 对 m<n 成立,则
T(n)≥4c(3n)log34+n=cnlog34+n≥cnlog34
于是,T(n)=Ω(nlog34) ;综上, T(n)=Θ(nlog34) 。
- 令 k=logn ,则 T(2k)=3T(2k/2)+k 。
令 S(k)=T(2k) ,则 S(k)=3S(k/2)+k 。
不难得到 S(k)=Θ(klog23) ,从而 T(n)=Θ((logn)log23) 。
Problem 2 (教材 4.4 节习题节选)
对递归式 T(n)=T(n−1)+T(n/2)+n ,利用递归树确定一个好的渐近上界,用代入法进行验证。
对递归式 T(n)=T(αn)+T((1−α)n)+cn ,利用递归树给出一个渐近紧确界,其中 0<α<1 和 c>0 是常数。
Solution
- T(n)=O(2n) 。
代入法验证:假设对于 m<n 有 T(m)≤2m ,则 T(n)≤2n−1+2n/2+n≤2n ,最后一步在 n 较大时成立。
为了说明 2n 是一个好的渐近上界,我们下面证明 T(n) 并不是多项式有界的。
反证法。若存在 c,k 使得 T(m)≤cmk+o(mk) ,使用代入法,应该有
T(n)≤c(n−1)k+c(2n)k+n=c(1+2k1)nk+o(nk)≤cnk+o(nk)
而 c(1+2k1)nk≤cnk 是不可能成立的,因此不存在这样的 c,k ,从而 T(n) 不是多项式有界的。
- 两个子问题的规模之和为 αn+(1−α)n=n ,这和归并排序是类似的,画递归树也能够看出这一点。于是,可以猜测 T(n)=Θ(nlogn) 。
先证下界。假设对 m<n 有 T(m)≥c1mlogm ,则
T(n)≥c1αnlog(αn)+c1(1−α)nlog((1−α)n)+cn=c1nlogn+n[c+c1(αlogα+(1−α)log(1−α))]≥c1nlogn
其中,最后一步需要 c1≤αlogα+(1−α)log(1−α)−c 。于是 T(n)=Ω(nlogn) 。
再证上界。假设对 m<n 有 T(m)≤c2mlogm ,则
T(n)≤c2αnlog(αn)+c2(1−α)nlog((1−α)n)+cn=c2nlogn+n[c+c2(αlogα+(1−α)log(1−α))]≤c2nlogn
其中,最后一步需要 c2≥αlogα+(1−α)log(1−α)−c 。于是 T(n)=O(nlogn) 。
综上, T(n)=Θ(nlogn) ,这是一个渐近紧确界。
Problem 3 (教材习题 4.5-1)
对下列递归式,使用主方法求出渐近紧确界。
T(n)=2T(n/4)+1
T(n)=2T(n/4)+n
T(n)=2T(n/4)+n
T(n)=2T(n/4)+n2
Solution
主定理情况 1 , T(n)=Θ(n) 。
主定理情况 2 , T(n)=Θ(nlogn) 。
主定理情况 3 , T(n)=Θ(n) 。
主定理情况 3 , T(n)=Θ(n2) 。
Problem 4 (教材习题 4.5-2)
熊教授想设计一个渐近快于 Strassen 算法的矩阵相乘算法。他的算法使用分治方法,将每个矩阵分解为 n/4×n/4 的子矩阵,分解和合并步骤共花费 Θ(n2) 时间。他需要确定,他的算法需要创建多少个子问题,才能击败 Strassen 算法。如果他的算法创建 a 个子问题,则描述运行时间 T(n) 的递归式为 T(n)=aT(n/4)+Θ(n2) 。 熊教授的算法如果要渐近快于 Strassen 算法, a 的最大整数值应是多少?
Solution
Strassen 算法的复杂度为 Θ(nlog27) 。因为要求 a 的最大值,考虑 a>16 的情况,用主方法可求得熊教授算法的复杂度为 Θ(nlog4a) 。如果熊教授的算法要渐近快于 Strassen ,那么需要 log4a<log27 ,解得 a<49 ,于是 a 的最大整数值为 48 。
Problem 5 (教材习题 4.5-5)
考虑主定理情况 3 的一部分:对某个常数 c<1 ,正则条件 af(n/b)≤cf(n) 是否成立。给出一个例子,其中常数 a≥1,b>1 且函数 f(n) 满足主定理情况 3 中除正则条件外的所有条件。
Solution
考虑 T(n)=T(n/3)+f(n) ,其中
f(n)={3n+23n,3n,if n=2i,i∈Notherwise
满足 f(n)=Ω(nlog31+ε)=Ω(nε) 的条件,但是不满足正则条件 f(n/3)≤cf(n),c<1 。
取 n=3⋅2i,i∈N ,有
f(n/3)=n+2n>3n=f(n)
是不满足正则条件的反例。
Problem 6 (教材习题 4.6-2)
证明:如果 f(n)=Θ(nlogbalogkn) ,其中 k≥0 ,那么主递归式的解为 T(n)=Θ(nlogbalogk+1n) 。为简单起见,假定 n 是 b 的幂。
Solution
证明:根据引理4.2(见第3讲PPT第44页,教材4.6节),有
T(n)=Θ(nlogba)+j=0∑logbn−1ajf(n/bj)
考虑和式
g(n)=j=0∑logbn−1ajf(n/bj)
由 f(n)=Θ(nlogbalogkn) 有
f(n/bj)=Θ((n/bj)logbalogk(n/bj))=Θ((nlogba/aj)(logblogb(n/bj))k)
于是
ajf(n/bj)=Θ(nlogbalogkblogbk(n/bj))=Θ(nlogba(logb(n)−j)k)=Θ(nlogbalogbk(n))
其中,最后一步用到了 j<logb(n) 。
继而
g(n)=j=0∑logbn−1ajf(n/bj)=Θ(j=0∑logbn−1nlogbalogbk(n))=Θ(nlogbalogbk+1(n))=Θ(nlogbalogk+1(n))
所以, T(n)=Θ(nlogbalogk+1n) 。
Problem 7 (教材习题 4.6-3)
证明:主定理中的情况 3 被过分强调了,从某种意义上来说,对于某个常数 c<1 ,正则条件 af(n/b)≤cf(n) 成立本身就意味着存在常数 ε>0 ,使得 f(n)=Ω(nlogba+ε) 。
Solution
证明:根据正则条件,不断迭代,有
f(n)≥caf(bn)≥(ca)2f(b2n)≥⋯≥(ca)if(bin)≥⋯≥(ca)logbnf(1)
则 f(n)=Ω((a/c)logbn)=Ω(nlogb(a/c))=Ω(nlogba+logb(1/c)) 。
取 ε=logb(1/c)>0,c<1 ,则 f(n)=Ω(nlogba+ε) 。