算法导论3.3 Exercises 答案
3.3-1
假设\(m\le n\)，那么根据\(f(n),g(n)\)的单调性，可以得到：
\(\begin{aligned} f(m)\le f(n)\\ g(m)\le g(n) \end{aligned}\)
那么得到\(f(m)+g(m)\le f(n)+g(n)\)，因此函数\(f(n)+g(n)\)是单调递增的。
由于\(g(m)\le g(n)\)，那么根据\(f\)的单调性，\(f(g(m))\le f(g(n))\)，因此函数\(f(g(n))\)是单调递增的。
在\(0\le g(n),0\le f(n)\)的基础上，那么有以下不等式：
\(0\le f(m)\cdot g(m)\le f(n)\cdot g(m)\le f(n)\cdot g(m)\)
因此函数\(f(n)\cdot g(n)\)是单调递增的。
3.3-2
\(\begin{aligned} \lfloor\alpha n\rfloor+\lceil(1-\alpha)n\rceil&=\lfloor\alpha n\rfloor+\lceil n-\alpha n\rceil\\ &=\lfloor\alpha n\rfloor+\lceil-\alpha n\rceil + n\\ &=\lfloor\alpha n\rfloor-\lfloor \alpha n\rfloor + n\\ &=n \end{aligned}\)
3.3-3
不难发现当\(k=0\)时结论成立。
考虑极限\(\displaystyle{\lim_{n\rightarrow\infty} \dfrac{(n+o(n))^k}{n^k}}\)的值。
\[\begin{aligned} \lim_{n\rightarrow\infty}\dfrac{(n+o(n))^k}{n^k}&=\lim_{n\rightarrow\infty}\left(1+\dfrac{o(n)}{n}\right)^k\\ &=1 \end{aligned}\]
因此有\((n+o(n))^k=\Theta(n^k)\)
由于\(n\le \lceil n\rceil < n+1\)，发现：
\(n^k=\Theta(n^k)\)
又因为\(1=o(n)\)，根据上面的结论，有\((n+1)^k=\Theta(n^k)\).
当\(k<0\)时，得到\((n+1)^k< \lceil n\rceil ^k\le n^k\)，由于\((n+1)^k=\Omega(n^k),n^k=O(n^k)\)，因此有\(\lceil n\rceil^k=\Theta(n^k)\)。
当\(k<0\)时，得到\(n^k\le \lceil n\rceil ^k< (n+1)^k\)，由于\((n+1)^k=O(n^k),n^k=\Omega(n^k)\)，因此有\(\lceil n\rceil^k=\Theta(n^k)\)。
综上所述，\(\lceil n\rceil^k=\Theta(n^k)\)。
\(\lfloor n\rfloor\)的证法类似，使用不等式\(n-1<\lfloor n\rfloor \le n\)即可。
3.3-4
a
\[a^{\lg _b c}=a^{\frac{\lg _a c}{\lg _a b}}=a^{\lg_a c\cdot \frac{1}{\lg _a b}}=c^{\frac{1}{\lg _a b}}=c^{\lg _b a}\]
b
对于\(n!=o(n^n)\)，考虑计算极限\(\displaystyle{\lim_{n\rightarrow +\infty} \dfrac{n!}{n^n}}\)的值，有
\[\begin{aligned} \lim_{n\rightarrow +\infty} \dfrac{n!}{n^n}&=\lim_{n\rightarrow +\infty}\dfrac{\sqrt{2\pi n} \left(\dfrac{n^n}{e^n}\right)\left(1+\Theta\left(\dfrac{1}{n}\right)\right)}{n^n}\\ &=\lim_{n\rightarrow +\infty}\dfrac{\sqrt{2\pi n}\left(1+\Theta\left(\dfrac{1}{n}\right)\right)}{e^n}\\ &=\lim_{n\rightarrow +\infty}\dfrac{\sqrt{2\pi n}\left(1+\Theta\left(\dfrac{1}{n}\right)\right)}{e^n}\\ &=\lim_{n\rightarrow +\infty}\dfrac{O\left(\frac{1}{\sqrt{n}}\right)}{e^n}\\ &=0 \end{aligned}\]
因此\(n!=o(n^n)\)。
对于\(n!=\omega(2^n)\)，考虑计算极限\(\displaystyle{\lim_{n\rightarrow +\infty} \dfrac{2^n}{n!}}\)的值，有
\[\begin{aligned} \lim_{n\rightarrow +\infty} \dfrac{2^n}{n!}&=\lim_{n\rightarrow +\infty}\dfrac{2^n}{\sqrt{2\pi n} \left(\dfrac{n^n}{e^n}\right)\left(1+\Theta\left(\dfrac{1}{n}\right)\right)}\\ &=\lim_{n\rightarrow +\infty}\dfrac{1}{\sqrt{2\pi n}\cdot \left(1+\Theta\left(\dfrac{1}{n}\right)\right)}\cdot \left(\dfrac{2e}{n}\right)^n\\ &\le\lim_{n\rightarrow +\infty}\left(\dfrac{2e}{n}\right)^n\\ &=0 \end{aligned}\]
因此\(n!=\omega(2^n)\)。
对于\(\lg n!=\Theta(n\lg n)\)，有
\[\begin{aligned} \lg n!&=\lg \sqrt{2\pi n} + n\lg n-n\lg e+\lg\left(1+\Theta\left(\dfrac{1}{n}\right)\right) \\ &=\Theta(\lg n)+\Theta(n\lg n)+ \Theta(n) + \Theta\left(\dfrac{1}{n}\right)\\ &=\Theta(n\lg n) \end{aligned}\]
因此\(\lg n!=\Theta(n\lg n)\)。
c
假设\(f(n)=\lg(\Theta(n))\)，那么\(\exists c_1,c_2,n_0,\forall n\ge n_0,0\le \lg (c_1 n)\le f(n)\le \lg (c_2n)\)成立，也就是
\[\lg c_1+\lg n\le f(n)\le \lg c_2 + \lg n\]
由于\(c_1,c_2\)是常数，因此\(\lg c_1+\lg n=\Omega(\lg n),\lg c_2=O(\lg n)\)，因此\(f(n)=\Theta(\lg n)\)。
假设\(f(n)=\Theta(\lg n)\)，那么\(\exists c_1,c_2,n_0,\forall n\ge n_0,0\le c_1\lg n\le f(n)\le c_2\lg n\)成立。由于\(\lg n=\lg \Theta(n)\)，也就是有\(\lg n=\lg \Omega(n),\lg n=\lg O(n)\)，因此\(f(n)=\lg \Theta(n)\)。
最终，\(\lg(\Theta(n))=\Theta(\lg n)\)
\(\star\) 3.3-5
证明一个函数\(f(n)\)是多项式有界的等价于证明\(\lg f(n)=O(\lg n)\)。原因如下：
充分性：根据定义，如果\(f(n)\)是多项式有界的，那么\(\exists c,k,n_0\in \mathbb{R}^{+},\forall n\ge n_0,0\le f(n)\le cn^k\)均成立。不失一般性，假设\(c\ge 1\)，因为\(c<1\)意味着\(f(n)\le n^k\)成立。假设\(n_0\ge 2\)，那么有：
\(\lg f(n)\le \lg c + k\lg n\le (\lg c+k)\lg n\)
因此有\(\lg f(n)=O(\lg n)\)
必要性：如果\(\lg f(n)=O(\lg n)\)，那么\(\exists c,n_0\in \mathbb{R}^{+},\forall n\ge n_0,0\le f(n)\le \lg n\)。那么就有
\(0\le f(n)=2^{\lg f(n)}\le 2^{c\lg n}=n^c\)
因此\(f(n)\)是多项式有界的。
最终使用如上结论来求解本题。
这道题首先基于两个前置结论：
- \(\lg(n!)=\Theta(n\lg n)\)
- \(\lceil \lg n\rceil=\Theta(\lg n)\)，因为当\(n\ge 2\)时，满足\(\lg n\le \lceil \lg n\rceil \le \lg n+1\le 2\lg n\)
最终，可以得到：
\(\begin{aligned} \lg(\lceil\lg n\rceil!)&=\Theta(\lceil\lg n\rceil\cdot \lg(\lceil\lg n\rceil))\\ &=\Theta((\lg n)\cdot (\lg \lg n))\\ &=\omega(\lg n) \end{aligned}\)
由于\(\lg(\lceil\lg n\rceil!)\neq O(\lg n)\)，因此\(\lceil\lg n\rceil!\)不是多项式有界的。
\(\begin{aligned} \lg(\lceil\lg\lg n\rceil!)&=\Theta(\lceil\lg\lg n\rceil\cdot \lg(\lceil\lg\lg n\rceil))\\ &=\Theta((\lg\lg n)\cdot (\lg\lg\lg n))\\ &=o((\lg\lg n)^2)\\ &=o(\lg n) &\text{(A)}\\ &=O(\lg n) \end{aligned}\)
变换\(A\)使用了结论：对于所有正数\(a,b\)，都有\(\lg^b n'=o(n'^a)\)。因此代入\(b=2,a=1,n'=\lg n\)得到最后一步。
由于\(\lg(\lceil\lg\lg n\rceil!)= O(\lg n)\)，因此\(\lceil\lg\lg n\rceil!\)是多项式有界的。
\(\star\) 3.3-6
相比于\(\lg^{\ast}n\)，\(\lg^{\ast}(\lg n)\)的迭代次数恰好少\(1\)，因为\(n\)进行一次迭代后就变成了 \(\lg n\)。因此，\(\lg^{\ast}(\lg n)=\lg^{\ast}n-1\)。
令\(t=\lg^{\ast}n,\displaystyle{\lim_{n\rightarrow +\infty} \lg^{\ast}n =+\infty}\)，因此有：
\[\begin{aligned} \lim_{n\rightarrow+\infty} \dfrac{\lg(\lg ^{\ast}n)}{\lg^{\ast}(\lg n)}&=\lim_{n\rightarrow+\infty} \dfrac{\lg(\lg ^{\ast}n)}{\lg^{\ast} n-1}\\ &=\lim_{t\rightarrow+\infty} \dfrac{\lg t}{t-1}\\ &=0 \end{aligned}\]
因此，\(\lg(\lg ^{\ast}n)\)的渐进增长速率要比\(\lg^{\ast}(\lg n)\)慢。
3.3-7
可以得到\(\phi\cdot \hat{\phi}=-1,\phi+\hat{\phi}=1\)。
以\(\phi,\hat{\phi}\)这两个值为解的一元二次方程可以构造出来：\((x-\phi)(x-\hat{\phi})=0\)
将左边展开后，有\(x^2-(\phi+\hat{\phi})x+\phi\cdot\hat{\phi}\)，代入后得到\(x^2-x-1\)。
那么最终可以构造出原一元二次方程\(x^2=x+1\)。
3.3-8
\(\phi=\dfrac{1+\sqrt{5}}{2},\hat{\phi}=\dfrac{1-\sqrt{5}}{2}\)
由于\(\phi,\hat{\phi}\)是方程\(x^2=x+1\)的根，因此\(\phi^2=\phi+1,\hat{\phi}^2=\hat{\phi}+1\)。
考虑使用数学归纳法证明。
首先，\(F_0=\dfrac{\phi^0-\hat{\phi}^0}{\sqrt{5}}=0\)，符合条件；
\(F_1=\dfrac{\phi^1-\hat{\phi}^1}{\sqrt{5}}=\dfrac{\sqrt{5}}{\sqrt{5}}=1\)，符合条件。
假设\(F_{i-1}=\dfrac{\phi^{i-1}-\hat{\phi}^{i-1}}{\sqrt{5}},F_{i-2}=\dfrac{\phi^{i-2}-\hat{\phi}^{i-2}}{\sqrt{5}}\)均成立，那么计算\(F_{i-2}+F_{i-1}\)，有
\[\dfrac{\phi^{i-1}+\phi^{i-2}-(\hat{\phi}^{i-1}+\hat{\phi}^{i-2})}{\sqrt{5}}=\dfrac{(\phi+1)\phi^{i-2}-(\hat{\phi}+1)(\hat{\phi}^{i-2})}{\sqrt{5}}=\dfrac{\phi^i-\hat{\phi}^i}{\sqrt{5}}=F_i\]
因此原式\(F_i\)得证。
3.3-9
\(k\lg k =\Theta(n)\)，意味着\(n=\Theta(k\lg k)\)。
那么\(\lg n=\Theta(\lg (k\cdot \lg k))=\Theta(\lg k+\lg \lg k)=\Theta(\lg k)\)。
因此有\(\dfrac{n}{\lg n}=\Theta\left(\dfrac{k\lg k}{\lg k}\right)=\Theta(k)\).
最终得到\(k=\Theta(n/\lg n)\)。