算法导论3 Problems 答案

3-1

a

不失一般性，本题将证明$p(n)=O(n^d)$，因为对于$\forall k\ge d,n^d=O(n^k)$均成立。

那么此时证明$\exists c,n_0>0,\forall n\ge n_0,0\le p(n)\le cn^d$成立。

那么对$p(n)\le cn^d$两边同时除上$n^d$，得到

$c\ge ad+\dfrac{a{d-1}}{n}+\dfrac{a_{d-2}}{n^2}+\dots+\dfrac{a_0}{n^d}$

也就是$c-ad\ge \dfrac{a{d-1}}{n}+\dfrac{a_{d-2}}{n^2}+\dots+\dfrac{a_0}{n^d}$

如果令$c-ad=1$，那么说明可以构造出$n_0$满足$\max{i=1}^d\left{\dfrac{a_{d-i}}{n_0^i}\right}\le\dfrac{1}{d}$。

也就是说，$n0=\max{i=1}^d {\sqrt[i]{d\cdot a_{d-i}}}$。

如上构造出的$(c,n_0)$，说明$p(n)=O(n^d)$。

问题b,c,d,e的证明方式类似，此处不再赘述。

3-2

$$\begin{array}{|l|l|l|l|l|l|l|} \hline A & B & O & o & \Omega & \omega &\Theta\\ \hline \lg^k n & n^{\epsilon} & \texttt{yes}&\texttt{yes}&\texttt{no} & \texttt{no} & \texttt{no}\\ \hline n^k & c^n & \texttt{yes}&\texttt{yes}&\texttt{no} & \texttt{no} & \texttt{no}\\ \hline \sqrt{n} & n^{\sin n} & \texttt{no}&\texttt{no}&\texttt{no} & \texttt{no} & \texttt{no}\\ \hline 2^n & 2^{n/2} & \texttt{no}&\texttt{no}&\texttt{yes} & \texttt{yes} & \texttt{no}\\ \hline n^{\lg c} & c^{\lg n} & \texttt{yes}&\texttt{no}&\texttt{yes} & \texttt{no} & \texttt{yes}\\ \hline \lg(n!) & \lg(n^n) & \texttt{yes}&\texttt{no}&\texttt{yes} & \texttt{no} & \texttt{yes}\\ \hline \end{array}$$

显而易见，随着$n$的增大，$n^{\sin n}$不是渐进增长的，一直在震荡。没有任何函数能够以它为界限。

根据等式$3.21$，有$n^{\lg c} = c^{\lg n}$，因此第四行的两个式子实际上是相同的。

3-3

a

增长速度从大到小如下：

$$\begin{aligned} &2^{2^{n+1}}\\ &2^{2^n}\\ &(n+1)!\\ &n!\\ &e^n\\ &n\cdot 2^n\\ &2^n\\ &(3/2)^n\\ &(\lg n)^{\lg n},n^{\lg \lg n}\\ &(\lg n)!& \qquad(A)\\ &n^3\\ &n^2,4^{\lg n}\\ &n\lg n,\lg(n!)\\ &n,2^{\lg n}\\ &\sqrt{2}^{\lg n}&\qquad(B)\\ &2^{\sqrt{2\lg n}}\\ &\lg ^2 n\\ &\ln n\\ &\sqrt{\lg n}\\ &\ln \ln n\\ &2^{\lg^{\ast} n}\\ &\lg^{\ast}n,\lg^{\ast}(\lg n)&\qquad(C)\\ &\lg(\lg^{\ast} n)\\ & n^{1/\lg n},1&\qquad(D)\\ \end{aligned}$$

$(A)$式可以根据斯特林公式如下化简：

$(\lg n)!=\sqrt{2\pi\lg n}\dfrac{(\lg n)^{\lg n}}{e^{\lg n}}\left(1+\Theta\left(\dfrac{1}{n}\right)\right)=\dfrac{\sqrt{2\pi \lg n}}{n} (\lg n)^{\lg n} \left(1+\Theta\left(\dfrac{1}{n}\right)\right)$

由此发现，其渐进增长速度低于$(\lg n)^{\lg n}$。

$(B)$式化简后的结果为$\sqrt{n}$。

对于$(C)$式子，相比于$\lg^{\ast}n$，$\lg^{\ast}(\lg n)$的迭代次数恰好少$1$，因为$n$进行一次迭代后就变成了 $\lg n$。因此，$\lg^{\ast}(\lg n)=\lg^{\ast}n-1=\Theta(\lg^{\ast}n)$。

$(D)$式可以如下化简：$n^{1/\lg n}=n^{\log_n 2}=2=\Theta(1)$

b

$f(n)=3^{2^{n+1}}\cdot (n\bmod 2)$。可以发现，$f(n)\neq \Omega(1)$，因为$f(n)=0$也成立。同样的，$f(n)\neq O(2^{2^{n+1}})$也成立。根据符号$O,\Omega$的传递性，可以知道$f(n)$满足题意。

3-4

a

不正确。

若$f(n)=n,g(n)=n^2$，那么虽然$f(n)=O(g(n))$，但是$g(n)\neq O(f(n))$。

b

不正确。

若$f(n)=n,g(n)=n^2$，那么虽然$f(n)=g(n)=n^2+n=\Theta(n^2)\neq n$，此时$f(n)+g(n)\neq \min{f(n)+g(n)}$。

c

正确。

$f(n)=O(g(n))$意味着$\exists c,n_0>0,\forall n\ge n_0,0\le f(n)\le cg(n)$成立。不失一般性，假设$c>1$，那么$\lg f(n)\le \lg c+\lg g(n)\le(\lg c+1)\lg g(n)$成立。那么，新构造出来的一对$(\lg c+1,n_0)$说明$\lg f(n)=O(\lg g(n))$。

d

不正确。

令$f(n)=2n,g(n)=n$，虽然$f(n)=O(g(n))$，但是$4^n\neq O(2^n)$，也就是$2^{f(n)}\neq O(2^{g(n)})$。

e

先决条件：如果$f(n)\ge 1$恒成立，那么就是正确的。

$f(n)=O(f^2(n))$意味着$\exists c,n_0>0,\forall n\ge n_0,0\le f(n)\le cf^2(n)$成立。基于先决条件，这个不等式是正确的。

f

正确。

$f(n)=O(g(n))$意味着$\exists c,n_0>0,\forall n\ge n_0,0\le f(n)\le cg(n)$成立。也就是说，$0\le \dfrac{f(n)}{c}\le g(n)$成立。那么新构造出来的一对$\left(\dfrac{1}{c},n_0\right)$说明$g(n)=\Omega(f(n))$。

g

不正确。

假设$f(n)=2^n$，那么$2^n\neq \Theta(2^{n/2})$，因此$f(n)\neq \Theta(f(n/2))$。

h

令$g(n)=o(f(n))$，那么意味着$\exists c,n_0,\forall n\ge n_0,0\le g(n)< cf(n)$成立。那么得到如下不等式：

$0\le f(n)\le f(n)+g(n)< (c+1) f(n)$

那么新构造出的一对$(c+1,n_0)$，说明$f(n)+o(f(n))=\Theta(f(n))$成立。

3-5

a

由$\Theta$符号的自反性可得：$f(n)=\Theta(f(n))=\Theta(\Theta(f(n)))$。

b

令$g(n)=\Theta(f(n)),h(n)=O(f(n))$，那么：

• $\exists c_1,c_2,n_1>0,\forall n\ge n_1,0\le c_1f(n)\le g(n)\le c_2f(n)$成立。
• $\exists c,n_2>0,\forall n\ge n_2,0\le h(n)\le cf(n)$成立。

令$n’=\max(n_1,n_2)$，那么$\forall n\ge n’$，以下不等式成立。

$$0\le c_1f(n)\le g(n)+h(n)\le (c+c_2)f(n)$$

那么新构造出来的$(c_1,c+c_2,n’)$说明$g(n)+h(n)=\Theta(f(n))$，即$\Theta(f(n))+O(f(n))=\Theta(f(n))$。

c

令$p(n)=\Theta(f(n)),q(n)=\Theta(g(n))$，那么：

• $\exists c_1,c_2,n_1>0,\forall n\ge n_1,0\le c_1f(n)\le p(n)\le c_2f(n)$成立。
• $\exists c_3,c_4,n_2>0,\forall n\ge n_2,0\le c_3g(n)\le q(n)\le c_4g(n)$成立。

令$n’=\max(n_1,n_2)$，那么$\forall n\ge n’$，以下不等式成立。

$$0\le \min(c_1,c_3)\cdot(f(n)+g(n))\le c_1f(n)+c_3g(n)\le p(n)+q(n)\le c_2f(n)+c_4g(n)\le \max(c_2,c_4)\cdot (f(n)+g(n))$$

那么新构造出来的$(\min(c_1,c_3),\max(c_2,c_4),n’)$说明$p(n)+q(n)=\Theta(f(n)+g(n))$，即$\Theta(f(n))+\Theta(g(n))=\Theta(f(n)+g(n))$

d

令$p(n)=\Theta(f(n)),q(n)=\Theta(g(n))$，那么：

• $\exists c_1,c_2,n_1>0,\forall n\ge n_1,0\le c_1f(n)\le p(n)\le c_2f(n)$成立。
• $\exists c_3,c_4,n_2>0,\forall n\ge n_2,0\le c_3g(n)\le q(n)\le c_4g(n)$成立。

令$n’=\max(n_1,n_2)$，那么$\forall n\ge n’$，以下不等式成立。

$$0\le c_1\cdot c_3\cdot f(n) \cdot g(n)\le p(n)\cdot q(n)\le c_2\cdot c_4\cdot f(n) \cdot g(n)$$

那么新构造出来的$(c_1\cdot c_3,c_2\cdot c_4,n’)$说明$p(n)\cdot q(n)=\Theta(f(n)\cdot g(n))$，即$\Theta(f(n))\cdot\Theta(g(n))=\Theta(f(n)\cdot g(n))$。

e

考虑计算极限 $\displaystyle{\lim_{n\rightarrow+\infty}\dfrac{(a_1n)^{k_1} \lg^{k_2}(a_2n)}{n^{k_1}\lg^{k_2} n}}$ 的值。有

$\begin{aligned}
\lim{n\rightarrow+\infty}\dfrac{(a_1n)^{k_1} \lg^{k_2}(a_2n)}{n^{k_1}\lg^{k_2} n}&=\lim{n\rightarrow+\infty}\left(\dfrac{a1n}{n}\right)^{k_1} \left(\dfrac{\lg(a_2n)}{\lg n}\right)^{k_2}\
&=\lim{n\rightarrow+\infty}a_1^{k_1}\left(1+\dfrac{\lg a_2}{\lg n}\right)^{k_2}\
&=a_1^{k_1}
\end{aligned}$

当$a_1> 0$时，$a_1^{k_1}\neq 0$，因此$(a_1n)^{k_1} \lg^{k_2}(a_2n)=\Theta(n^{k_1}\lg^{k_2} n)$成立。

$\star$ f

令$g(n)=\Theta(f(n))$，那么$\exists c_1,c_2,n_1>0,\forall n\ge n_1,0\le c_1f(n)\le g(n)\le c_2f(n)$成立。

当$k < n_0$时，$g(k)=\Theta(1)$，为低阶项，不需要进行考虑。因此仅需要$\forall k\in S, k\ge n_1$时的情况。

那么对不等式每一个项进行求和，有$\displaystyle{0\le c1\sum{k\in S} f(k)\le \sum{k\in S} g(k)\le c_2\sum{k\in S} f(k)}$。

由此构造出来的${n1,c_1,c_2}$说明$\displaystyle{\sum{k\in S} g(k)=\Theta \left(\sum_{k\in S} f(k)\right)}$。

因此有$\displaystyle{\sum{k\in S} \Theta(f(k))=\Theta \left(\sum{k\in S} f(k)\right)}$。

$\star$ g

对于所有整数$n$，令$f(n)\equiv 1,g(n)\equiv \dfrac{1}{2}$，不难知道，$g(n)=\Theta(f(n))$。

那么有$\displaystyle{\prod{k\in S} g(k)=\prod{k\in S} \Theta(f(k))=\dfrac{1}{2^{|S|}}}$。

不难发现$\displaystyle{\prod{k\in S} g(k)=O\left(\prod{k\in S} f(k)\right)}=O(1)$，但是$\displaystyle{\prod{k\in S} g(k)\neq\Omega\left(\prod{k\in S} f(k)\right)}=\Omega(1)$。因为当集合$S$的大小区域无穷大时，$\displaystyle{\prod{k\in S} g(k)}$的值无限趋近于$0$，那么不存在正常数$c’$，使得对于无穷多的$S\subseteq \mathbb{Z},\displaystyle{\prod{k\in S} g(k)}\ge c’\prod_{k\in S} f(k)$成立。

此时有$\displaystyle{\prod{k\in S} \Theta(f(k))\neq \Theta\left(\prod{k\in S} f(k)\right)}$。

因此，对于所有整数$n$，令$f(n)\equiv 1,g(n)\equiv \dfrac{1}{2}$为一个反例。并且，无论$\displaystyle{\prod{k\in S} \Theta(f(k))}$还是$\displaystyle{\Theta\left(\prod{k\in S} f(k)\right)}$，它们都是收敛的。

3-6

a

如果$f(n)=\Theta(g(n))$，那么$f(n)=O(g(n)),f(n)=\Omega^{\infty}(g(n))$。

如果存在整数$c$，存在无穷多个$n,f(n)\ge cg(n)\ge0$成立，那么$f(n)=\Omega^{\infty}(g(n))$。

如果存在整数$c$，存在无穷多个$n,cg(n)\ge f(n)\ge0$成立，那么$f(n)=O(g(n))$。

如果存在整数$c$，就算存在有穷多个$n,f(n)\ge cg(n)\ge0$成立，那么随着$n\rightarrow + \infty,cg(n)\ge f(n)\ge0$成立。也就是$f(n)=O(g(n))$

b

可以构造出$f(n)=n^{1+\sin n},g(n)=n$，可以发现，$f(n)$和$g(n)$不能用于彼此渐进比较。

c

使用$\Omega^{\infty}$的优点：可以用于描述所有函数之间的渐近关系（如果有的话）。

缺点：无穷多个$n$和$n$趋于无穷这两种说法似乎有点区别，描述不够精确。

d

$f(n)=\Theta(g(n))$可以推导出$f(n)=O’(g(n)),f(n)=\Omega(g(n))$。

如果$f(n)=O’(g(n)),f(n)=\Omega(g(n))$，不能推导出$f(n)=\Theta(g(n))$。

e

$\tilde{\Omega}(g(n)):\exists c,k,n_0>0,\forall n\ge n_0,0\le cg(n)\lg ^k(n)\le f(n)$成立。

$\tilde{\Theta}(g(n)):\exists c_1,k_1,c_2,k_2,n_0>0,\forall n\ge n_0,0\le c_1g(n)\lg ^{k_1}(n)\le f(n)\le c_2g(n)\lg^{k_2}(n)$成立。

充分性：

将如上不等式提取出$0\le c_1g(n)\lg^{k_1}(n)\le f(n)$，那么$(c_1,k_1,n_0)$的存在性说明$f(n)=\tilde{\Omega}(g(n))$

将如上不等式提取出$0\le f(n)\le c_2g(n)\lg^{k_2}(n)$，那么$(c_2,k_2,n_0)$的存在性说明$f(n)=\tilde{O}(g(n))$

最终，充分性成立。

必要性：

对于$f(n)=\tilde{\Omega}(g(n))$，存在正数$n_1,c_1$使得对于所有使得对于所有$n\ge n_1,0\le c_1g(n)\lg^{k_1}(n)\le f(n)$成立。

对于$f(n)=\tilde{O}(g(n))$，存在正数$n_2,c_2$使得对于所有使得对于所有$n\ge n_2,0\le f(n)\le c_2g(n)\lg^{k_2}(n)$成立。

构造出$n’=\max(n_1,n_2)$，那么对于所有$0\le c_1g(n)\lg^{k_1}(n)\le f(n),0\le f(n)\le c_2g(n)\lg^{k_2}(n)$均成立，也就是$0\le c_1g(n)\lg ^{k_1}(n)\le f(n)\le c_2g(n)\lg^{k_2}(n)$。

那么新构造出的$(c_1,k_1,c_2,k_2,n’)$说明$f(n)=\tilde{\Theta}(g(n))$。

最终，必要性成立。

3-7

$$\begin{array}{|l|l|l|} \hline f(n) & c & f_c^{\ast}(n) \\ \hline n-1 & 0 & \Theta(n)\\ \hline \lg n & 1 & \Theta(\lg^{\ast} n)\\ \hline n/2 & 1 & \Theta(\lg n) \\ \hline n/2 & 2 & \Theta(\lg n)\\ \hline \sqrt{n} & 2 &\Theta(\lg \lg n)\\ \hline \sqrt{n} & 1 &\texttt{undefined} \\ \hline n^{1/3} & 2 &\Theta(\lg \lg n)\\ \hline \end{array}$$

对于问题e，根据迭代式子的定义，找到一个最小的$i$，使得以下式子成立：

$$n^{\frac{1}{2^i}}\le 2$$

两边取对$n$对数，得到$\dfrac{1}{2^i}\le \log_n 2$，也就是$2^i\ge \lg n$。两边再对$2$取对数，得到：

$$i\ge \lg\lg n$$

这个答案和问题g同理。

至于问题f，对于大于$1$的数，无论做多少次取根号迭代都无法小于等于$1$，因此无法取值。