算法导论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\logb 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\logb 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\logb n\rfloor} \lg^{-1}\left(\dfrac{n}{b^j}\right)\right)\
&=\Theta \left(n^{\log_b a}\sum{j=0}^{\lfloor\logb 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\logb 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\logb 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\logb 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\logb 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}$