算法导论4.7 Exercises 答案

\(\star\) 4.7-1

考虑使用归纳法的思想进行证明。

假设\(\exists n_0,\forall n \in (0,n_0]\)，构造出一个函数\(T'(n)\)使得\(T'(n)=cT(n)\)都成立。考虑证明\(\forall n\in (0,+\infty),T'(n)=cT(n)\)都成立。

令\(\displaystyle{b = \min_{i=1}^k b_i}\)。当\(n> n_0\)时，假设\(\forall m\in(0,n/b]\)时，\(T'(m)=cT(m)\)都成立，那么对于\(\forall n\in(n/b,n]，\)有

\(\begin{aligned} T'(n) &= cf(n)+\sum_{i=1}^k a_iT'(n/b_i)\\ &= cf(n)+\sum_{i=1}^k cT(n/b_i)\\ &= c\left(f(n)+\sum_{i=1}^k T(n/b_i)\right)\\ &=cT(n) \end{aligned}\)

因此根据归纳法，\(\forall n\in (0,+\infty),T'(n)=cT(n)\)都成立。

4.7-2

首先证明\(f(n)=n^2\)满足多项式增长条件。化简\(f(n)/d\le f(\varPsi n)\le df(n)\)，得到两个不等式：\(d\ge \dfrac{1}{\varPsi^2},d\ge \varPsi^2\)。取\(d(\varPsi)=\sqrt{\varPsi}\)。如果\(\forall 1 \le \varPsi\le \phi\)，不等式\(d\ge \dfrac{1}{\varPsi^2},d\ge \varPsi^2\)都成立，那么\(d\)需要满足\(d\ge \phi^2\)。此时令\(d\)有关于\(\phi\)的函数\(D(\phi)=\phi^2\)，\(d\)值存在并且仅依赖于\(\phi\)，因此函数\(f(n)=n^2\)是满足多项式增长条件。

接下来证明\(f(n)=2^n\)不满足多项式增长条件。化简\(f(n)/d\le f(\varPsi n)\le df(n)\)，得到两个不等式：\(d\ge 2^{(1-\varPsi)n},d\ge 2^{(\varPsi-1)n}\)。如果\(\forall 1 \le \varPsi\le \phi\)，不等式\(d\ge 2^{(1-\varPsi)n},d\ge 2^{(\varPsi-1)n}\)都成立，那么\(d\)需要满足\(d\ge 2^{(\phi-1)n}\)。由于确定好\(d\)值后，总能存在足够大的\(n\)，使得不等式\(d\ge 2^{(\phi-1)n}\)不成立。因此函数\(f(n)=2^n\)不满足多项式增长条件。

4.7-3

由于\(f(n)\)满足多项式增长条件，因此可以构造出一组\((d_0,\phi_0,\hat{n})\)，其中\(d_0> 1,\phi_0 \ge 1,\hat{n}>0\)，使得\(\forall n\ge \hat{n}\)，都有\(f(n)/d_0\le f(\phi_0 n)\le d_0f(n)\)成立。

那么得到\(d_0f(n)\ge f(n)/d_0\)，即\(f(n)\cdot\left(d_0-\dfrac{1}{d_0}\right)\ge 0\)。由于\(d_0>1\)，那么\(d_0-\dfrac{1}{d_0}>0\)，从而得到\(f(n)\ge 0\)。

那么构造出的这一组\((d_0,\phi_0,\hat{n})\)说明\(\forall n\ge \hat{n},f(n)\ge 0\)都成立，因此\(f(n)\)是渐进为正的。

\(\star\) 4.7-4

构造\(f(n)=n-\lfloor n\rfloor\)。可以发现\(f(\Theta(n))=\Theta(f(n))=\Theta(1)\)。

接下来证明\(f(n)\)不满足多项式增长条件。化简\(f(n)/d\le f(\varPsi n)\le df(n)\)，得到两个不等式：\(d\ge \dfrac{n-\lfloor n\rfloor}{\varPsi n-\lfloor\varPsi n\rfloor},d\ge \dfrac{\varPsi n-\lfloor\varPsi n\rfloor}{n-\lfloor n\rfloor}\)。

对于某个固定的\(\phi=\phi_0\)，此时\(d=d_0\)应该是个定值，那么考虑某个无理数\(\varPsi_0\le \phi_0\)。对于所有正整数\(n\)，当\(m\)从右向左无限趋近于\(n\)时，\(\dfrac{\varPsi_0 m-\lfloor\varPsi_0 m\rfloor}{m-\lfloor m\rfloor}\)将趋向于无穷大（因为\(\varPsi_0\)是无理数，分子\(\varPsi_0 m-\lfloor\varPsi_0 m\rfloor\)必定不会趋向于\(0\)）。

也就是说，存在无穷多个足够大的\(m\)，使得不等式\(d_0\ge\max\left\{ \dfrac{n-\lfloor n\rfloor}{\varPsi n-\lfloor\varPsi n\rfloor}, \dfrac{\varPsi n-\lfloor\varPsi n\rfloor}{n-\lfloor n\rfloor}\right\}\)不成立。因此，\(f(n)\)不满足多项式增长条件。

4.7-5

a

由于\(\displaystyle{\sum_{i=1}^k \dfrac{a_i}{b_i}=\dfrac{1}{2}+\dfrac{1}{3}+\dfrac{1}{6}=1}\)，因此\(p=1\)。并且由于\(f(n)=n\lg n\)。那么有

\(\begin{aligned} T(n)&=\Theta\left(n^p\left(1+\int_{1}^n \dfrac{f(x)}{x^{p+1}}dx\right)\right) \\ &=\Theta\left(n\left(1+\int_{1}^n \dfrac{\lg x}{x}dx\right)\right) \\ &=\Theta\left(n\left(1+\left(\left.\dfrac{\ln^2 x}{2\ln 2}\right|_{1}^n\right)\right)\right) \\ &=\Theta\left(n\left(1+\dfrac{\ln^2n}{2\ln 2}\right)\right) \\ &=\Theta(n\lg ^2n) \end{aligned}\)

b

由于\(\displaystyle{\sum_{i=1}^k \dfrac{a_i}{b_i}=\dfrac{3}{3}+\dfrac{8}{4}=3}\)，因此\(p>1\)。如果精确解方程\(\displaystyle{\sum_{i=1}^k \dfrac{a_i}{b_i^p}=1}\)，那么可以得到\(p\approx1.856738\)。并且由于\(f(n)=n^2/ \lg n\)。那么有

\(\begin{aligned} T(n)&=\Theta\left(n^p\left(1+\int_{1}^n \dfrac{f(x)}{x^{p+1}}dx\right)\right) \\ &=\Theta\left(n^p\left(1+\int_{1}^n \dfrac{x^{1-p}}{\lg x}dx\right)\right) \\ \end{aligned}\)

可以发现，直接使用Akra-Bazzi方法并不可行。

考虑使用普通的代入法求出。由于\(T(n)=3T(n/3)+8T(n/4)+n^2/\lg n\ge n^2/\lg n\)，因此有\(T(n)=\Omega(n^2/\lg n)\)。

假设\(T(n)\le cn^2/\lg n\)，那么有

\(\begin{aligned} T(n)&=3T(n/3)+8T(n/4)+n^2/\lg n\\ &\le \dfrac{c n^2}{3\lg (n/2)}+\dfrac{c n^2}{2\lg (n/4)}+\dfrac{n^2}{\lg n}\\ &\le \dfrac{c n^2}{3\lg (n/4)}+\dfrac{c n^2}{2\lg (n/4)}+\dfrac{n^2}{\lg (n/4)}\\ &= \left(\dfrac{5c}{6}+1\right) \dfrac{n^2}{\lg n - 2}\\ &\le \left(\dfrac{5c}{6}+1\right) \dfrac{n^2}{0.9\lg n}&\qquad(A)\\ &=\left(\dfrac{25c}{27}+\dfrac{10}{9}\right) \dfrac{n^2}{\lg n}\\ &\le \dfrac{cn^2}{\lg n} &\qquad(B)\\ \end{aligned}\)

其中，步骤\((A)\)假设了\(\lg n-2\ge 0.9\lg n\)，即\(n\ge 2^{20}\)，实际上不需要\(0.9\)，只需要这个数大于\(5/6\)且小于\(1\)即可。步骤\((B)\)假设了\(\dfrac{25c}{27}+\dfrac{10}{9}\le c\)，即\(c\ge 15\)。

因此如果满足\(c\ge 15\)的基础上，\(\forall n<2^{20}\)，都有\(c\ge \dfrac{T(n)\lg n}{n^2}\)。那么由数学归纳法，可以得到\(T(n)=O(n^2/\lg n)\)。

最终有\(T(n)=\Theta(n^2/\lg n)\)。遗憾的是，仍未知如何改变递推式的形式使其可以直接使用Akra-Bazzi方法。

c

由于\(\displaystyle{\sum_{i=1}^k \dfrac{a_i}{b_i}=\dfrac{4}{9}}\)，因此\(p<1\)。如果精确解方程\(\displaystyle{\sum_{i=1}^k \dfrac{a_i}{b_i^p}=1}\)，那么可以得到\(p=0\)。并且由于\(f(n)=\lg n\)。那么有

\(\begin{aligned} T(n)&=\Theta\left(n^p\left(1+\int_{1}^n \dfrac{f(x)}{x^{p+1}}dx\right)\right) \\ &=\Theta\left(1+\int_{1}^n \dfrac{\lg x}{x}dx\right)\\ &=\Theta\left(1+\left(\left.\dfrac{\ln^2 x}{2\ln 2}\right|_{1}^n\right)\right)\\ &=\Theta\left(1+\dfrac{\ln^2n}{2\ln 2}\right) \\ &=\Theta(\lg ^2 n) \end{aligned}\)

d

由于\(\displaystyle{\sum_{i=1}^k a_i=\dfrac{1}{3}}\)，因此\(p<0\)。如果精确解方程\(\displaystyle{\sum_{i=1}^k \dfrac{a_i}{b_i^p}=1}\)，那么可以得到\(p=-1\)。并且由于\(f(n)=1/n\)。那么有

\(\begin{aligned} T(n)&=\Theta\left(n^p\left(1+\int_{1}^n \dfrac{f(x)}{x^{p+1}}dx\right)\right) \\ &=\Theta\left(n^{-1}\left(1+\int_{1}^n \dfrac{1}{x}dx\right)\right) \\ &=\Theta\left(n^{-1}\left(1+\left(\left.\ln x\right|_{1}^n\right)\right)\right) \\ &=\Theta\left(n^{-1}\left(1+\ln n\right)\right) \\ &=\Theta\left(\dfrac{\lg n}{n}\right) \end{aligned}\)

e

由于\(\displaystyle{\sum_{i=1}^k \dfrac{a_i}{b_i}=3}\)，因此\(p>1\)。如果精确解方程\(\displaystyle{\sum_{i=1}^k \dfrac{a_i}{b_i^p}=1}\)，那么可以得到\(p=3\)。并且由于\(f(n)=n^2\)。那么有

\(\begin{aligned} T(n)&=\Theta\left(n^p\left(1+\int_{1}^n \dfrac{f(x)}{x^{p+1}}dx\right)\right) \\ &=\Theta\left(n^{3}\left(1+\int_{1}^n \dfrac{1}{x^2}dx\right)\right) \\ &=\Theta\left(n^{3}\left(1+\left(\left.-\dfrac{1}{x^2}\right|_{1}^n\right)\right)\right) \\ &=\Theta\left(n^{3}\left(2-\dfrac{1}{n^2}\right)\right) \\ &=\Theta\left(n^3\right) \end{aligned}\)

\(\star\) 4.7-6

证明的过程将由两部分组成：先证明\(n_0=1\)时的情况，再通过\(n_0=1\)时的情况推广到\(n_0>1\)时的情况。由于第二部分的证明过程和定理4.4的证明过程完全相同，因此此处只使用Akra-Bazzi方法证明第一部分。

连续主定理中，子问题只有一个项。因此解方程\(\dfrac{a}{b^p}=1\)，得到\(p=\log_b a\)。接下来同样地分三种情况进行考虑。

1

证明如果\(\exists \epsilon>0,f(n)=O(n^{\log_b a-\epsilon})\)，那么\(T(n)=\Theta(n^{\log_b a})\)。

由于此处假定了\(n_0=1\)，因此\(\exists c>0,\forall n\ge 1,f(n)\le cn^{\log_b a-\epsilon}\)成立。那么代入

\(\begin{aligned} n^p\left(1+\int_{1}^n \dfrac{f(x)}{x^{p+1}}dx\right)&\le n^{\log_b a}\left(1+\int_1^n\dfrac{cx^{\log_b a-\epsilon}}{x^{\log_b a+1}}dx\right)\\ &= n^{\log_b a}\left(1+\int_1^n cx^{-\epsilon-1}dx\right)\\ &= n^{\log_b a}\left(1+c\left(\left.\dfrac{x^{-\epsilon}}{-\epsilon}\right|_{1}^{n}\right)\right)\\ &= n^{\log_b a}\left(1+\dfrac{c}{\epsilon}(1-n^{-\epsilon})\right)\\ &= n^{\log_b a}(1+O(1))\\ \end{aligned}\)

因此有\(T(n)=O(n^{\log_b a})\)。注意这里不使用\(\Theta\)符号，因为前面进行了放缩。

再根据\(\displaystyle{n^p\left(1+\int_{1}^n \dfrac{f(x)}{x^{p+1}}dx\right)\ge n^p}\)，那么得到\(T(n)=\Omega(n^{\log_b a})\)。

最终得到\(T(n)=\Theta(n^{\log_b a})\)。

2

证明如果\(k\ge 0,f(n)=\Theta(n^{\log_b a}\lg^k n)\)，那么\(T(n)=\Theta(n^{\log_b a} \lg^{k+1} n)\)。

那么有

\(\begin{aligned} T(n)&=\Theta\left(n^p\left(1+\int_{1}^n \dfrac{f(x)}{x^{p+1}}dx\right)\right)\\ &=\Theta\left(n^{\log_b a}\left(1+\Theta\left(\int_{1}^n \dfrac{f(x)}{x^{\log_b a+1}}dx\right)\right)\right)\\ &=\Theta\left(n^{\log_b a}\left(1+\Theta\left(\int_{1}^n \dfrac{x^{\log_b a}\lg^{k} x}{x^{\log_b a+1}}dx\right)\right)\right)\\ &=\Theta\left(n^{\log_b a}\left(1+\Theta\left(\int_{1}^n \dfrac{\lg^{k} x}{x}dx\right)\right)\right)\\ &=\Theta\left(n^{\log_b a}\left(1+\Theta\left(\ln 2\cdot\int_{1}^n \lg^{k} x d\lg x\right)\right)\right)\\ &=\Theta\left(n^{\log_b a}\left(1+\Theta\left(\lg^{k+1}x\right)\right)\right)\\ &=\Theta\left(n^{\log_b a}\left(1+\lg^{k+1}x\right)\right)\\ &=\Theta\left(n^{\log_b a}\lg^{k+1}x\right)\\ \end{aligned}\)

3

这一部分的证明沿用引理4.2，引理4.3的证明，证明步骤完全一致，此处忽略。

最终，将如上结论代入定理4.4中的推广到\(n_0>1\)的情况，整个证明完成。