Problem 1 (教材习题 4-3)
(更多的递归式例子) 对下列每个递归式,给出 T(n) 的渐近上界和下界。假定对足够小的 n , T(n) 是常数。给出尽量紧确的界,并验证其正确性。
T(n)=4T(n/3)+nlogn
T(n)=3T(n/3)+n/logn
T(n)=4T(n/2)+n2n
T(n)=3T(n/3−1)+n/2
T(n)=2T(n/2)+n/logn
T(n)=T(n/2)+T(n/4)+T(n/8)+n
T(n)=T(n−1)+1/n
T(n)=T(n−1)+logn
T(n)=T(n−2)+1/logn
T(n)=nT(n)+n
Solution
主定理情况 1 , T(n)=Θ(nlog34) 。
T(n)=O(nlogn) 且对于任意的 ε>0 ,T(n)=Ω(n1−ε) 。
首先,用代入法证明 T(n)≤cnlogn 。
假设 T(m)≤cmlogm 对于 m<n 成立,则
T(n)≤3c3nlog(n/3)+lognn=cnlogn+(logn1−clog3)n≤cnlogn
最后一步取 c≥1/log3 即可。
再用代入法证明,对于任意 ε>0 , T(n)≥cn1−ε 。
假设 T(m)≥cm1−ε 对于 m<n 成立,则
T(n)≥3c(3n)1−ε+lognn≥3εcn1−ε+dnεn=(3εc+d1)n1−ε≥cn1−ε
倒数第 3 步用的是 logn=o(nε) (见课本3.2节);最后一步取 d≤1/c 即可。
综上,T(n)=O(nlogn) 且对于任意的 ε>0 ,T(n)=Ω(n1−ε) 。
主定理情况 3 , T(n)=Θ(n2n) 。
T(n)=Θ(nlogn) ,根据主定理情况 2 猜测,使用代入法证明。
和第 2 问类似, T(n)=O(nlogn) 且 ∀ε>0,T(n)=Ω(n1−ε) 。
T(n)=Θ(n) ,用代入法即可证明。
不妨 T(1)=1 ,则
T(n)=i=1∑ni1≤1+∫1nx1dx=1+lnn
T(n)=i=1∑ni1≥∫1n+1x1dx=ln(n+1)
于是 T(n)=Θ(logn) 。
- 不妨 T(1)=1 ,则
T(n)=1+i=1∑nlogi=1+log(n!)=Θ(nlogn)
最后一步回忆练习2-2问题2。
- 和前面两问类似,不难理解
T(n)=Θ(∫0nlogn1)=Θ(li(n))=Θ(lognn)
其中, li(n) 是对数积分函数。
- 换元法。令 n=2k ,有
T(2k)=2k/2T(2k/2)+2k⇔2kT(2k)=2k/2T(2k/2)+1
⇔2kT(2k)=Θ(logk)⇔T(2k)=Θ(2klogk)
于是不难得到, T(n)=Θ(nloglogn) 。
Problem 2 (教材习题 4-4)
(佩波那契数) 本题讨论递归式 F0=0,F1=1,Fi=Fi−1+Fi−2,i≥2 定义的佩波那契数的性质。我们将使用生成函数技术来求解佩波那契递归式。 生成函数(又称为 形式幂级数 )F 定义为
F(z)=i=0∑∞Fizi=0+z+z2+2z3+3z4+5z5+8z6+13z7+21z8+...
其中 Fi 为第 i 个佩波那契数。
证明:F(z)=z+zF(z)+z2F(z) 。
证明:
F(z)=1−z−z2z=(1−ϕz)(1−ϕ^z)z=51(1−ϕz1−1−ϕ^z1)
其中
ϕ=21+5=1.61803⋯,ϕ^=21−5=−0.61803⋯
- 证明:
F(z)=i=0∑∞51(ϕi−ϕ^i)zi
- 利用上述结果证明: 对 i>0,Fi=5ϕi ,结果舍入到最接近的整数。(提示:观察到 ∣ϕ^∣<1 。)
Solution
- 证明:从右往左化简,利用递归式 Fi−1+Fi−2=Fi 。
z+zF(z)+z2F(z)=z+zi=0∑∞Fizi+z2i=0∑∞Fizi=z+i=1∑∞Fi−1zi+i=2∑∞Fi−2zi=0+z+i=2∑∞(Fi−1+Fi−2)zi=i=0∑∞Fizi=F(z)
- 证明:基于第1问,从两边往中间化简。
F(z)=z+zF(z)+z2F(z)⇔F(z)=1−z−z2z
51(1−ϕz1−1−ϕ^z1)=5(1−ϕz)(1−ϕ^z)(ϕ−ϕ^)z
其中,ϕ+ϕ^=1,ϕ−ϕ^=5,ϕϕ^=−1 。
于是
51(1−ϕz1−1−ϕ^z1)=(1−ϕz)(1−ϕ^z)z=1−(ϕ+ϕ^)z+ϕϕ^z2z=1−z−z2z=F(z)
- 证明:考虑几何级数,有
i=0∑∞xi=1−x1
于是
i=0∑∞51(ϕi−ϕ^i)zi=51(i=0∑∞(ϕz)i−i=0∑∞(ϕ^z)i)=51(1−ϕz1−1−ϕ^z1)=F(z)
- 证明:根据 F(z) 的定义及第 3 问结论,
F(z)=i=0∑∞Fizi=i=0∑∞51(ϕi−ϕ^i)zi
于是 Fi=(ϕi−ϕ^i)/5 。观察到 ∣ϕ^∣<1 ,则 ∣ϕ^/5∣<0.5 。于是,在就近舍入的意义下,Fi=ϕi/5 。
Problem 3 (教材习题 4-5)
(芯片检测) 熊教授有 n 片可能完全一样的集成电路芯片,原理上可以用来相互检测。教授的测试夹具同时只能容纳两块芯片。当夹具装载上时,每块芯片都检测另一块,并报告它是好是坏。一块好的芯片总能准确报告另一块芯片的好坏,但教授不能信任坏芯片报告的结果。因此,4种可能的测试结果如下:
芯片A的结果 |
芯片B的结果 |
结论 |
B是好的 |
A是好的 |
两片都是好的,或都是坏的 |
B是好的 |
A是坏的 |
至少一块是坏的 |
B是坏的 |
A是好的 |
至少一块是坏的 |
B是坏的 |
A是坏的 |
至少一块是坏的 |
证明:如果超过 n/2 块芯片是坏的,使用任何基于这种逐对检测操作的策略,教授都不能确定哪些芯片是好的。假定坏芯片可以合谋欺骗教授。
考虑从 n 块芯片中寻找一块好芯片的问题,假定超过 n/2 块芯片是好的。证明:进行 ⌊n/2⌋ 次逐对检测足以将问题规模减半。
假定超过 n/2 块芯片是好的,证明:可以用 Θ(n) 次逐对检测找出好的芯片。给出描述检测次数的递归式,并求解它。
Solution
- 证明:记好芯片的数量为 g<n/2 ,则坏芯片的数量 n−g>g 。
考虑所有好芯片的集合 G ,一定存在一个坏芯片的集合 B ,满足 ∣B∣=∣G∣ ,因为坏芯片的数量是比好芯片多的。下面证明我们无论如何都不能区分 G 和 B 中的芯片。
给出 B 中坏芯片的合谋策略:如果被比较的芯片是 B 中的,则报告好芯片;如果被比较的芯片是 G 中的,则报告坏芯片。
于是, G 和 B 中的芯片就都说自己集合里面的是好芯片,对方集合里面的是坏芯片了。从而,无论怎么测试,对于 G 和 B 中的每个芯片都有 g−1 个芯片认为它是好的;都有 g 个芯片认为它是坏的,因此大家的评价结果都一样,无法区分。
- 证明:下面给出一个通过 ⌊n/2⌋ 次检测将问题规模减半的算法。
上述算法显然使得规模减半了,下面证明剩下的芯片依旧满足好的芯片比坏的芯片多这个性质,从而我们得到了一个规模减半的子问题。
原本是好芯片比坏芯片多的,在上述算法中我们进行的两种操作下:
第一种操作:如果检测结果表明其中至少一块是坏的,则将这两块芯片都扔掉;
- 我们要么同时扔掉两个坏芯片,要么扔掉了一个坏芯片和一个好芯片,这两种情况都没有破坏“好芯片比坏芯片多”的性质。
第二种操作:如果检测结果表明要么是两个好芯片,要么是两个坏芯片,则随便扔掉一块;
- 因为剩下的要么都是好的,要么都是坏的,所有检测对都随便扔掉一个,相当于好芯片和坏芯片都变成原来的一半,也没有破坏“好芯片比坏芯片多”的性质。
最后对奇数的情况补充一些接受,奇数个芯片,将一个芯片放在一旁之后:
综上,我们可以通过 ⌊n/2⌋ 次检测将问题规模减半。
- 证明:先给出一个找出一个好芯片的算法。
基础情况:n=1,2 时,一定都是好芯片,直接返回即可(因为好芯片要比坏芯片多);
递归情况:不断地重复问题 2 中的折半算法,直到问题规模缩小到 1 或者 2 为止。
该算法的递归式为 T(n)≤T(n/2)+⌊n/2⌋ ,根据主定理的情况 3 不难得出 T(n)=O(n) 。
根据找到的这一个好的芯片和所有其他芯片比对,可以找出所有的好芯片,需要 Θ(n) 次逐对检测。
所以,可以用 O(n)+Θ(n)=Θ(n) 次逐对检测找出所有的好芯片。
Problem 4 (教材习题 4-6)
(Monge 阵列) 对一个 m×n 的实数阵列 A ,若对所有满足 1≤i<k≤m 和 1≤j<l≤n 的 i,j,k,l 有
A[i,j]+A[k,l]≤A[i,l]+A[k,j]
则称 A 是 Monge 阵列 (Monge Array)。换句话说,无论何时选出 Monge 阵列的两行和两列,对于交叉点上的 4 个元素,左上和右下两个元素之和总是小于等于左下和右上元素之和。例如,下面就是一个 Monge 阵列:
1017241145367517222813443366131622632195128293417372153232324723634
- 证明:一个数组是 Monge 阵列当且仅当对所有 i=1,2,...,m−1 和 j=1,2,...,n−1 ,有
A[i,j]+A[i+1,j+1]≤A[i,j+1]+A[i+1,j]
(提示:对于“当”的部分,分别对行和列使用归纳法。)
- 下面数组不是 Monge 阵列。改变一个元素使其变成 Monge 阵列。(提示:利用第 1 问的结果。)
37215332432363413212273091532103168
令 f(i) 表示第 i 行的最左最小元素的列下标。证明:对任意 m×n 的 Monge 阵列, f(1)≤f(2)≤...≤f(m) 。
下面是一个计算 m×n 的 Monge 阵列 A 每一行最左最小元素的分治算法的描述:
提取 A 的偶数行构造其子矩阵 A′ 。递归地确定 A′ 每行的最左最小元素。然后计算 A 的奇数行的最左最小元素。
解释如何在 O(m+n) 时间内计算 A 的奇数行的最左最小元素(在偶数行的最左最小元素已知的情况下)。
- 给出第 4 问中描述的算法的运行时间的递归式。证明其解为 O(m+nlogm) 。
Solution
- 证明:充分性显然,取 k=i+1,l=j+1 即可。下面证明必要性。
分别对行和列进行归纳以拓展 A[i,j]+A[i+1,j+1]≤A[i,j+1]+A[i+1,j] 。
固定 i 和 j ,先进行行拓展,证明: A[i,j]+A[i+r,j+1]≤A[i,j+1]+A[i+r,j] 。
基础情况: r=1 时显然成立。
归纳假设:假设 A[i,j]+A[i+r,j+1]≤A[i,j+1]+A[i+r,j] 。
归纳步骤:下面证明 A[i,j]+A[i+r+1,j+1]≤A[i,j+1]+A[i+r+1,j]
A[i,j]+A[i+r+1,j+1]=(A[i,j]+A[i+r,j+1])+(A[i+r,j]+A[i+r+1,j+1])−A[i+r,j+1]−A[i+r,j]≤(A[i,j+1]+A[i+r,j])+(A[i+r,j+1]+A[i+r+1,j])−A[i+r,j+1]−A[i+r,j]=A[i,j+1]+A[i+r+1,j]
固定 i ,j 和 k ,再进行列拓展,证明: A[i,j]+A[i+r,j+c]≤A[i,j+c]+A[i+r,j] 。
基础情况: c=1 时已经证毕,显然成立。
归纳假设:假设 A[i,j]+A[i+r,j+c]≤A[i,j+c]+A[i+r,j] 。
归纳步骤:下面证明 A[i,j]+A[i+r,j+c+1]≤A[i,j+c+1]+A[i+r,j]
A[i,j]+A[i+r,j+c+1]=(A[i,j]+A[i+r,j+c])+(A[i,j+c]+A[i+r,j+c+1])−A[i+r,j+c]−A[i,j+c]≤(A[i,j+c]+A[i+r,j])+(A[i+r,j+c]+A[i,j+c+1])−A[i+r,j+c]−A[i,j+c]=A[i,j+c+1]+A[i+r,j]
综上,我们证明了 A[i,j]+A[i+r,j+c]≤A[i,j+c]+A[i+r,j] ,令 k=i+r,l=j+c ,即证明了 A[i,j]+A[k,l]≤A[i,l]+A[k,j] 。必要性得证。
将第 2 行第 3 列的 7 改成 5。
证明:反证法。若存在 f(i)>f(i+1) ,令 k=f(i),j=f(i+1) ,有 j<k 。
由于 f(i) 表示的是第 i 行最左最小元素的列下标,我们有 A[i,j]>A[i,k],A[i+1,k]>A[i+1,j] ,于是 A[i,j]+A[i+1,k]>A[i,k]+A[i+1,j] ,与 Monge 阵列定义矛盾。
- 以 m 是奇数为例说明, m 是偶数的情况也是类似的。
线性扫描 A[i,f(i−1)..f(i+1)] 取最小值即可得到 f(i) ,需要访问数组 A f(i+1)−f(i−1)+1 次,其中 i=1,3,5,7,... 。
记 f(0)=1 表示第一行从最左边开始扫描, f(m+1)=n 表示最后一行一直扫描到最后。于是,总的访问次数为:
i=1,3,5,7,...,m∑f(i+1)−f(i−1)+1=f(m+1)−f(0)+2m=n+2m−1=O(m+n)
所以上述扫描行为的运行时间为 O(m+n) 。
- 第 4 问中的算法对应的递归式为 T(m,n)=T(m/2,n)+c(m+n) ,下面用代入法证明 T(m,n)=O(m+nlogm) 。
假设 T(m,n)≤d(m+nlogm) 对于较小的 m 成立,则
T(m,n)≤d(m/2+nlog(m/2))+c(m+n)=(c+d/2)m+dnlogm+(c−d)n≤d(m+nlogm)
其中,最后一步需要 c≤d/2。 T(m,n)=O(m+nlogm) 证毕。