算法导论4.3 Exercises 答案
4.3-1
a
假设\(T(n)\le cn^2\)，那么有
\(\begin{aligned} T(n)&=T(n-1)+n\\ &\le c(n-1)^2+n\\ &\le c(n^2-n+1)\\ &\le cn^2 \end{aligned}\)
令\(c=\max(1,T(1)),n_0=1\)。由于\(T(1)\le c\le cn^2\)，那么由数学归纳法，原结论\(T(n)=O(n^2)\)成立。
b
假设\(T(n)\le c\lg (n-d)\)，那么有
\(\begin{aligned} T(n)&=T(n/2)+\Theta(1)\\ &\le c\lg (n / 2 - d)+\Theta(1)\\ &=c\lg (n / 2 - d) + c - c+\Theta(1)\\ &=c(\lg (n / 2 - d) + 1) - c+\Theta(1)\\ &=c\lg (n - 2d) - c+\Theta(1)\\ &=c\lg (n - 2d) & \qquad(A)\\ &\le c\lg (n-d) & \qquad (B) \end{aligned}\)
其中，步骤\((A)\)假设\(c\)充分大，大于\(\Theta(1)\)的上界时，那么\((A)\)步骤就成立。步骤\((B)\)假设\(d>0\)。
如果\(n_0=2\)，那么\(c\)的值仍需比\(T(2),T(3)\)大。由数学归纳法，原结论\(T(n)=O(\lg n)\)成立。
c
假设\(T(n)\le cn\lg n\)，那么有
\(\begin{aligned} T(n)&=2T(n/2)+n\\ &\le 2c(n/2)\lg (n/2) + n\\ &=cn\lg (n/2) + n\\ &=cn\lg n - cn + n\\ &=cn\lg n-(c-1) n\\ &\le cn\lg n \end{aligned}\)
假设\(n_0=2\)，那么令\(c=\max\{1,T(2)/2,T(3)/(3\lg 3)\}\)，由数学归纳法，\(T(n)=O(n\lg n)\)成立。
假设\(T(n)\ge c'n\lg n\)，那么有
\(\begin{aligned} T(n)&=2T(n/2)+n\\ &\ge 2c'(n/2)\lg (n/2) + n\\ &=c'n\lg (n/2) + n\\ &=c'n\lg n - c'n + n\\ &=c'n\lg n-(c'-1) n\\ &\ge c'n\lg n \end{aligned}\)
假设\(n_0=2\)，那么令\(c=\min\{1,T(2)/2,T(3)/(3\lg 3)\}\)。由数学归纳法，\(T(n)=\Omega(n\lg n)\)成立。
因此，\(T(n)=\Theta(n\lg n)\)。
d
可以发现，当\(n/2+17\le 2n/3\)时，即有\(n\ge102\)，因此，我们假设\(n\ge 102\)。假设\(T(n)\le cn\lg n-d-en-f\lg n\)，那么有
\(\begin{aligned} T(n)&=2T(n/2+17)+n\\ &=2c(n/2+17) \lg(n/2+17)-2d-2en-2f\lg n+n\\ &=c(n+34) \lg(n/2+17)-2d-2en-2f\lg n+n\\ &=cn\lg(n/2+17)+34c\lg(n/2+17) -2d-2en-2f\lg n+n\\ &\le cn\lg(3n/4)+34c\lg(3n/4) -2d-2en-2f\lg n+n\\ &=cn\lg n+cn\lg(3/4) + 34 c\lg n+34c\lg(3/4)-2d-2en-2f\lg n+n\\ &=cn\lg n-(2e-(c\lg(3/4)+1)) n-(2f-c\lg(3/4))\lg n-(2d-34c\lg(3/4))\\ &\le cn\lg n-d-en-f\lg n &\qquad(A) \end{aligned}\)
其中，步骤\((A)\)假设了\(2e-(c\lg(3/4)+1)\ge e,2f-c\lg(3/4)\ge f,2d-34c\lg(3/4)\ge d\)。
因此，只需要确定好\(c=\max\{1,T(102)/(102\lg 102),T(103)/(103\lg103)\}\)，那么就可以确定好\(d,e,f\)的值。由数学归纳法，\(T(n)=O(n\lg n)\)成立。
e
假设\(T(n)\le (c-d)n\)，那么有
\(\begin{aligned} T(n)&=2T(n/3)+\Theta(n)\\ &\le \dfrac{2c-2d}{3}n+\Theta(n)\\ &=\dfrac{2c+d}{3}n+(\Theta(n)-dn)\\ &\le \dfrac{2c+d}{3}n&\qquad(A)\\ &\le (c-d)n&\qquad(B) \end{aligned}\)
其中步骤\((A)\)是假定了\(dn\)是\(\Theta(n)\)的上限值，因此可以消去。步骤\((B)\)则是假设\(\dfrac{2c+d}{3}\le c-d\)，即\(c\ge 5d\)。
此外\(c\)值还需要超过\(\max\{1,T(1)+d,T(2)/2+d\}\)。由数学归纳法，\(T(n)=O(n)\)成立。
假设\(T(n)\ge c'n\)，那么有
\(\begin{aligned} T(n)&=2T(n/3)+\Theta(n)\\ &\ge \dfrac{2c'}{3}n+\Theta(n)\\ &\ge \dfrac{2c'}{3}n&\qquad(A)\\ &\ge c'n\\ \end{aligned}\)
其中步骤\((A)\)使用了渐进函数的函数值都非负的事实。
因此只要令\(c'=\min\{1,T(1),T(2)/2\}\)。由数学归纳法，\(T(n)=\Omega(n)\)成立。
因此，\(T(n)=\Theta(n)\)。
f
假设\(T(n)\le cn^2 - dn\)，那么有
\(\begin{aligned} T(n)&=4T(n/2)+\Theta(n)\\ &\le 4(c(n/2)^2 - d(n/2))+\Theta(n)\\ &=cn^2-2dn +\Theta(n)\\ &=cn^2-dn +(\Theta(n)-dn)\\ &\le cn^2-dn &\qquad(A) \end{aligned}\)
其中步骤\((A)\)是假定了\(dn\)是\(\Theta(n)\)的上限值，因此可以消去。
那么令\(c=\max\{1,T(1)+d,(T(2)+2d)/4\}\)。由数学归纳法，\(T(n)=O(n^2)\)成立。
假设\(T(n)\ge c'n^2\)，那么有
\(\begin{aligned} T(n)&=4T(n/2)+\Theta(n)\\ &\ge c'n^2+\Theta(n)\\ &\ge c'n^2&\qquad(A) \end{aligned}\)
其中步骤\((A)\)使用了渐进函数的函数值都非负的事实。
那么令\(c'=\max\{1,T(1),T(2)/4\}\)。由数学归纳法，\(T(n)=\Omega(n^2)\)成立。
因此，\(T(n)=\Theta(n^2)\)。
4.3-2
假设\(T(n)\le cn^2\)，那么有
\(\begin{aligned} T(n)&=4T(n/2)+n\\ &\le 4 c(n/2)^2+n\\ &=cn^2+n \end{aligned}\)
最终得出的是\(T(n)\le cn^2+n\)，无法得到\(T(n)\le cn^2\)。
重新考虑\(T(n)\le cn^2 - dn\)，那么有
\(\begin{aligned} T(n)&=4T(n/2)+n\\ &\le 4(c(n/2)^2 - d(n/2))+n\\ &=cn^2+(1-2d)n\\ &\le cn^2-dn &\qquad(d\ge 1) \end{aligned}\)
取好\(d\)后，令\(c=\max\{1,T(1)+d,(T(2)+2d)/4\}\)。由数学归纳法，\(T(n)=O(n^2)\)成立。
4.3-3
假设\(T(n)\le c2^n\)，那么有
\(\begin{aligned} T(n)&=2T(n-1)+1\\ &\le 2c\cdot 2^{n-1}+1\\ &=c2^n+1 \end{aligned}\)
最终得出的是\(T(n)\le c2^n+1\)，无法得到\(T(n)\le c2^n\)。
重新考虑\(T(n)\le c2^n-d\)，那么有
\(\begin{aligned} T(n)&=2T(n-1)+1\\ &\le 2(c\cdot 2^{n-1}-d)+1\\ &=c2^n-(2d-1)\\ &\le c2^n-d & \qquad(A) \end{aligned}\)
其中步骤\((A)\)假设了\(2d-1\ge d\)，即\(d\ge 1\)。
确定好\(d\)值后，令\(c=\max\{1,(T(1)+d)/2\}\)。由数学归纳法，\(T(n)=O(2^n)\)成立。