算法导论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 a_d+\dfrac{a_{d-1}}{n}+\dfrac{a_{d-2}}{n^2}+\dots+\dfrac{a_0}{n^d}\)

也就是\(c-a_d\ge \dfrac{a_{d-1}}{n}+\dfrac{a_{d-2}}{n^2}+\dots+\dfrac{a_0}{n^d}\)

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

也就是说，\(n_0=\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{a_1n}{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 c_1\sum_{k\in S} f(k)\le \sum_{k\in S} g(k)\le c_2\sum_{k\in S} f(k)}\)。

由此构造出来的\(\{n_1,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\)，因此无法取值。