算法导论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/bi)\
&= 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^{\logb a+1}}dx\right)\right)\right)\
&=\Theta\left(n^{\log_b a}\left(1+\Theta\left(\int{1}^n \dfrac{x^{\logb 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^{\logb 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$的情况，整个证明完成。