算法导论4.6 Exercises 答案

4.6-1

\(\begin{aligned} \sum_{j=0}^{\lfloor\log_b n\rfloor}(\log_b n-j)^k&\ge \sum_{j=0}^{\lfloor\log_b n\rfloor}(\lfloor\log_b n\rfloor-j)^k\\ &=\sum_{j=0}^{\lfloor\log_b n\rfloor}j^k\\ &=\Omega(\lfloor\log_b n\rfloor^{k+1}) \end{aligned}\)

因此，最终有\(\displaystyle{\sum_{j=0}^{\lfloor\log_b n\rfloor}(\log_b n-j)^k=\Omega(\log_b^{k+1} n)}\)。

\(\star\) 4.6-2

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

我们希望得出的结论是\(f(n)=\Omega(n^{\log_b a+\epsilon})\)，即\(\exists d,n_0,\epsilon,\forall n\ge n_0,f(n)\ge dn^{\log_b a+\epsilon}\)均成立。

根据正则条件，假设\(\forall n\ge n_0, f(n)\ge \dfrac{a}{c} f\left(\dfrac{n}{b}\right)\)成立。令\(m=\dfrac{n}{b}\)，可以得到\(f(bm)\ge \dfrac{a}{c} f(m)\)，如果假设\(m\)也是足够大的，再联立\(f(m)\ge \dfrac{a}{c} f\left(\dfrac{m}{b}\right)\)，那么可以得到\(f(b^2m)\ge \left(\dfrac{a}{c}\right)^2 f(m)\)。最终经过多重迭代，可以得到\(f(b^im)\ge \left(\dfrac{a}{c}\right)^i f(m)\)，其中\(i\)是一个正整数。

任意指定好\(n_0\)的值后（可以随意指定，如\(n_0=1\)），令\(d\)为函数\(g(n)=\dfrac{f(n)}{n^{\log_b a+\epsilon}}\)在区间\([n_0,b\cdot n_0)\)上的最小值，那么我们构造除了一组\((n_0,d)\)，对于\(\forall n\in[n_0,b\cdot n_0),f(n)\ge dn^{\log_b a+\epsilon}\)均成立。

那么考虑\(n>b\cdot n_0\)时的情况。可以发现每一个\(n\)都可以写成\(n=x\cdot b^i\)，其中\(i\)是一个正整数，\(x\in[n_0,b\cdot n_0)\)。那么有\(f(n)\ge \left(\dfrac{a}{c}\right)^if(x)\)。那么由于\(f(x)\ge dx^{\log_b a+\epsilon}\)成立。那么有接下来的变化：

\(\begin{aligned} f(n) &\ge \left(\dfrac{a}{c}\right)^if(x)\\ &\ge \left(\dfrac{a}{c}\right)^i dx^{\log_b a+\epsilon}\\ &=\left(\dfrac{a}{c}\right)^i d\left(\dfrac{n}{b^i}\right)^{\log_b a+\epsilon}\\ &=d \cdot \dfrac{n^{\log_b a+\epsilon}}{a^i\cdot b^{i\epsilon}}\\ &=d \cdot \dfrac{n^{\log_b a+\epsilon}}{c^i\cdot b^{i\epsilon}}\\ &= d \cdot n^{\log_b a+\epsilon} & \qquad(A) \end{aligned}\)

其中步骤\((A)\)将\(\epsilon\)构造除了满足\(c^i\cdot b^{i\epsilon}=1\)的值，对于所有\(i\)第成立。这个值为\(\epsilon=-\log_b c\)。

那么，我们构造出了一组值\(n_0,d,\epsilon\)，使得\(\forall n\ge n_0,f(n)\ge dn^{\log_b a+\epsilon}\)都成立。即有\(f(n)=\Omega(n^{\log_b a+\epsilon})\)。

\(\star\) 4.6-3

本题需要基于一个假设才能运算：\(n\)不是\(b\)的整数次幂，否则\(g(n)=+\infty\)。原因如下：

如果\(n\)是\(b\)的整数次幂，那么\(\lfloor\log_b n\rfloor=\log_b n\)。\(g(n)\)中的最后一项是\(a^{\lfloor\log_b n\rfloor}\left(\dfrac{n}{b^{\lfloor\log_b n\rfloor}}\right)^{\log_b a}\lg^{-1}\left(\dfrac{n}{b^{\lfloor\log_b n\rfloor}}\right)\)，化简后得到\(a^{\log_b n}\lg^{-1}(1)\)。注意\(\lg^{-1}(1)=+\infty\)。因此，本题需要有开头的那段假设才能进行。

如果\(n\)不是\(b\)的整数次幂，那么有

\(\begin{aligned} g(n)&=\Theta\left(\sum_{j=0}^{\lfloor\log_b n\rfloor} a^j\left(\dfrac{n}{b^j}\right)^{\log_b a}\lg^{-1}\left(\dfrac{n}{b^j}\right)\right)\\ &=\Theta \left(n^{\log_b a}\sum_{j=0}^{\lfloor\log_b n\rfloor} \dfrac{a^j}{b^{j\log_b a}}\lg^{-1}\left(\dfrac{n}{b^j}\right)\right)\\ &=\Theta \left(n^{\log_b a}\sum_{j=0}^{\lfloor\log_b n\rfloor} \lg^{-1}\left(\dfrac{n}{b^j}\right)\right)\\ &=\Theta \left(n^{\log_b a}\sum_{j=0}^{\lfloor\log_b n\rfloor} \left(\dfrac{\log_b (n/b^j)}{\log_b 2}\right)^{-1}\right)\\ &=\Theta \left(n^{\log_b a}\sum_{j=0}^{\lfloor\log_b n\rfloor} \dfrac{\log_b 2}{\log_b n-j}\right)\\ &=\Theta \left(n^{\log_b a}\cdot \log_b 2\cdot\sum_{j=0}^{\lfloor\log_b n\rfloor} \dfrac{1}{\log_b n-j}\right)\\ &=\Theta \left(n^{\log_b a}\sum_{j=0}^{\lfloor\log_b n\rfloor} \dfrac{1}{\log_b n-j}\right)\\ \end{aligned}\)

接下来的问题是证明\(\displaystyle{\sum_{j=0}^{\lfloor\log_b n\rfloor} \dfrac{1}{\log_b n-j}=\Theta(\lg \lg n)}\)。

首先证明\(\displaystyle{\sum_{j=0}^{\lfloor\log_b n\rfloor} \dfrac{1}{\log_b n-j}=\Omega(\lg \lg n)}\)。可以知道有：

\(\begin{aligned} \sum_{j=0}^{\lfloor\log_b n\rfloor} \dfrac{1}{\log_b n-j}&\ge \sum_{j=0}^{\lfloor\log_b n\rfloor} \dfrac{1}{\lfloor\log_b n\rfloor+1 -j}\\ &=\sum_{j=1}^{\lfloor\log_b n\rfloor+1} \dfrac{1}{j}\\ &=\ln(\lfloor\log_b n\rfloor+1) + O(1) \\ &=\Omega(\lg \lg n) \end{aligned}\)

因此有\(\displaystyle{\sum_{j=0}^{\lfloor\log_b n\rfloor} \dfrac{1}{\log_b n-j}=\Omega(\lg \lg n)}\)。

可以知道函数\(\displaystyle{f(j)=\sum_{j=0}^{\lfloor\log_b n\rfloor} \dfrac{1}{\log_b n-j}}\)是一个递减函数，那么有

\(\begin{aligned} \sum_{j=0}^{\lfloor\log_b n\rfloor} \dfrac{1}{\log_b n-j}&\le \int_{-1}^{\lfloor\log_b n\rfloor} \dfrac{1}{\log_b n-x}dx\\ &=\left.-\ln(\log_b n-x)\right|_{-1}^{\lfloor\log_b n\rfloor}\\ &=\ln(\log_b n+1)-\ln(\log_b n-\lfloor\log_b n\rfloor)\\ &=O(\lg \lg n) \end{aligned}\)

因此有\(\displaystyle{\sum_{j=0}^{\lfloor\log_b n\rfloor} \dfrac{1}{\log_b n-j}=O(\lg \lg n)}\)。

最终\(\displaystyle{\sum_{j=0}^{\lfloor\log_b n\rfloor} \dfrac{1}{\log_b n-j}=\Theta(\lg \lg n)}\)得证。

那么有\(g(n)=\Theta(n^{\log_b a} \cdot\Theta(\lg\lg n))=\Theta(n^{\log_b a}\lg\lg n)\)。

最终，\(T(n)=\Theta(n^{\log_b a})+\Theta(n^{\log_b a}\lg \lg n)=\Theta(n^{\log_b a}\lg \lg n)\)。

对于以上结论，都是假定了\(T,g\)中所隐含的\(n_0\)都满足\(n_0=1\)。

假设真正的主递推式\(U(n)=aU(n/b)+n/\lg n\)，对于\(n_0\neq 1\)，有

\(U(n)=\left\{\begin{aligned} &\Theta(1) & & \text{if}\quad n< n_0 \\ &aU(n/b)+n/\lg n & & \text{if}\quad n\ge n_0 \\ \end{aligned}\right.\)

那么有

\(\begin{aligned} U(n)&=T(n/n_0)\\ &=\Theta((n/n_0)^{\log_b a})+\Theta((n/n_0)^{\log_b a} \lg\lg n/n_0)\\ &=\Theta(n^{\log_b a})+\Theta(n^{\log_b a}\lg \lg n)\\ &=\Theta(n^{\log_b a}\lg \lg n) \end{aligned}\)