算法导论课后习题解析第三章

悠悠 2021-11-01 09:16 388阅读 0赞

3.1-1  
分情况讨论  
当$f(n) \\ge g(n)$时，$max(f(n), g(n))=f(n)$，存在$c\_1=\\frac 12,c\_2=1,n\_0>0$使得 $$0 < c\_1(f(n)+g(n)) \\le f(n) \\le c\_2(f(n)+g(n)) 对于所有n \\ge n\_0$$ 同理可证当$g(n) > f(n)$的情况

3.1-2  
$(n+a)^b = n^b + c\_1 n^\{b-1\} + c\_2 n^\{b-2\} + \\cdots + a^b=\\theta (n^b)$

3.1-3  
大O表示法用来表示一个算法复杂度的上界，而“至少”一词用来形容下界，所以这句话的意思是该算法复杂度的上界只要不小于$O(n^2)$即可，相当于没有说明算法的复杂度的界限，没有意义。

3.1-4  
$2^\{n+1\} = O(2^n)$  
证明：存在$c=2, n\_0>0$使得 $$0 \\le 2^\{n+1\} \\le c2^n 对于所有n \\ge n\_0$$ $2^\{2n\} \\not = O(2^n)$  
证明：假设存在$c,n\_0$使得 $$\\eqalign\{ & 0 \\le 2^\{2n\} \\le c2^n 对于所有n \\ge n\_0 \\\\ & \\Rightarrow 2^n \* 2^n \\le c 2^n \\\\ & \\Rightarrow 2^n \\le c \}$$ 由于不存在常数c使得等式成立，故产生矛盾，得证。

3.1-5  
利用定义就可以直接证明

3.1-6  
最坏情况下复杂度为$O(g(n))$说明所有情况时间复杂度为$O(g(n))$，最好情况下时间复杂度为$\\Theta(g(n))$说明所有情况时间复杂度为$\\Omega(g(n))$，根据定理3.1得算法时间复杂度为$\\Theta (g(n))$

3.1-7  
$f(n)=o(g(n))$说明对于任意正常数$c,n\_0$，对于所有的$n \\ge n\_0$都有$$0 \\le f(n) < cg(n) 对于所有n \\ge n\_0$$ 这时假设$f(n)=\\omega (g(n))$，说明对于任意正常数$c,n\_0$，对于所有的$n \\ge n\_0$都有$$0 \\le cg(n) < f(n)$$ 然而这样的常数c是存在的，故产生矛盾，可得$o(g(n)) \\cap \\omega (g(n)) = \\Phi$。

3.1-8  
$$\\eqalign\{\\Omega(g(m, n))= \\\{ f(m, n): & 存在大于零的常数c,n\_0,m\_0 \\cr & 使得 0 \\le cg(n,m) \\le f(n, m) \\cr & 对于所有n \\ge n\_0 或 m \\ge m\_0 \\\}\}$$ $$\\eqalign\{\\Theta(g(m, n))=\\\{f(m, n): & 存在大于零的常数c\_1,c\_2,n\_0,m\_0 \\cr & 使得0\\le c\_1g(n,m) \\le f(n, m) \\le c\_2g(n,m) \\cr & 对于所有n \\ge n\_0 或 m \\ge m\_0 \\\} \}$$

3.2-1  
由于f(n)和g(n)单调递增，所以对于任意$x\_1 < x\_2$，都有$$f(x\_1) < f(x\_2)$$ $$g(x\_1) < g(x\_2)$$所以$$f(x\_1)+g(x\_1) < f(x\_2)+g(x\_2)$$ $$f(g(x\_1)) < f(g(x\_2))$$ 如果当f(x)和g(x)都非负时显然有$$f(x\_1)\*g(x\_1) < f(x\_2)\*g(x\_2)$$

3.2-2  
$$\\lg \{a^\{\\log\_bc\}\}=\\log\_bc \\lg a=\\frac \{\\lg a \\lg c\} \{\\lg b\}$$ $$\\lg \{c^\{\\log\_ba\}\}=\\log\_ba \\lg c=\\frac \{\\lg a \\lg c\} \{\\lg b\}$$ $$\\Rightarrow a^\{\\log\_bc\} = c^\{\\log\_ba\}$$

3.2-3  
证明$\\lg \{(n!)\} = \\Theta (n \\lg n)$： $$\\lg \{n!\} = \\sum\_\{i=1\}^n\{\\lg i\} < \\sum\_\{i=1\}^n\{\\lg n\} = n \\lg n$$ $$\\sum\_\{i=1\}^n\{\\lg i\} = \\sum\_\{i=1\}^\{n/2\} \{\[\\lg i + \\lg \{(n-i)\}\]\} = \\sum\_\{i=1\}^\{n/2\} \{\[\\lg \{i (n-i)\}\]\} > \\sum\_\{i=1\}^\{n/2\} \{\\lg \{\\frac \{n^2\}\{4\}\}\} = n \\lg n - n = \\frac 12 n \\lg n$$ $$\\Rightarrow \\lg \{(n!)\} = \\Theta (n \\lg n)$$ 证明$n! = \\omega (2^n)$： $$\\because 当n > 4时，i (n-i) > 2^2$$ $$\\therefore n! = \\prod\_\{i=1\}^\{n/2\} \{i (n-i)\} > \\prod\_\{i=1\}^\{n/2\} \{2^2\} = 2^n$$ $$\\therefore n! = \\omega (2^n)$$ 证明$n! = o (n^n)$： $$\\because 当n > 1时，n! = \\prod\_\{i=1\}^n i < \\prod\_\{i=1\}^n n = n^n$$ $$\\therefore n! = o (n^n)$$

3.2-4  
证明$f(n)$是否多项式有界等价于证明$\\lg \{f(n)\} = O (\\lg n)$，这是因为如果$f(n)$多项式有界，则存在正常数$c,k,n\_0$使得对于所有的$n > n\_0$都有$f(n) < c n^k$，即$\\lg \{f(n)\} < k c \\lg n$，所以$\\lg \{f(n)\} = O \{\\lg n\}$，反之亦然。  
对于$\\lceil \\lg n \\rceil !$我们有 $$\\lg \{(\\lceil \\lg n \\rceil !)\} = \\Theta (\\lceil \\lg n \\rceil \\lg \{\\lceil \\lg n \\rceil\}) = \\Theta (\\lg n \\lg \{\\lg n\}) = \\omega (\\lg n)$$ $\\lceil \\lg n \\rceil !$ 非多项式有界  
  
对于 $ \\lceil \\lg \{\\lg n\} \\rceil ! $ 我们有 $$\\eqalign \{ & \\lg \{(\\lceil \\lg \{\\lg n\} \\rceil !)\} \\\\ & = \\Theta (\\lceil \\lg \{\\lg n\} \\rceil \\lg \{\\lceil \\lg \{\\lg n\} \\rceil\}) \\\\ & = \\Theta (\\lg \{\\lg n\} \\lg \{\\lg \{\\lg n\}\}) \\\\ & = o ((\\lg \{\\lg n\})^2) \\\\ & = o(\\lg n)\} $$ $ \\lceil \\lg \{\\lg n\} \\rceil ! $ 多项式有界

3.2-5  
$$\\lg^\* \{\\lg n\} = \\lg^\* n - 1 > \\lg \{\\lg^\* n\},当\\lg^\* n > 2时$$

3.2-6  
$$\\phi ^2 = (\\frac \{1+\\sqrt 5\} \{2\})^2 = \\frac \{3 + \\sqrt5\} \{2\} = \\phi + 1$$ $$\\hat \{\\phi\} ^2 = (\\frac \{1-\\sqrt 5\} \{2\})^2 = \\frac \{3 - \\sqrt5\} \{2\} = \\hat \{\\phi\} + 1$$

3.2-7  
证明：  
当i = 0时， $$\\frac \{\\phi ^0 - \\hat \{\\phi\}^0\}\{\\sqrt 5\} = 0 = F\_0$$ 当i = 1时， $$\\frac \{\\phi ^1 - \\hat \{\\phi\}^1\}\{\\sqrt 5\} = 1 = F\_1$$ 假设当i = k-1和i = k时都满足公式，则当i = k+1时 $$F\_\{k+1\}=F\_k + F\_\{k-1\} = \\frac \{(\\phi ^k + \\phi ^\{k-1\}) - (\\hat \{\\phi\}^k+\\hat \{\\phi\}^\{k-1\})\}\{\\sqrt 5\}=\\frac \{\\phi^\{k-1\}(\\phi + 1)-\\hat \{\\phi\}^\{k-1\}(\\hat \{\\phi\} + 1)\}\{\\sqrt 5\}=\\frac \{\\phi ^\{k+1\} - \\hat \{\\phi\}^\{k+1\}\}\{\\sqrt 5\}$$

3.2-8  
这题要用到性质$g(n) = \\Theta (f(n)) \\Leftrightarrow f(n) = \\Theta (g(n))$，所以$k \\ln k = \\Theta (n) \\Leftrightarrow n = \\Theta (k \\ln k)$， 要证$k = \\Theta (n / \\ln n)$等价于证$n / \\ln n = \\Theta (k)$，代入条件得 $$\\frac \{n\}\{\\ln n\} = \\Theta (\\frac \{k \\ln k\} \{\\ln \{(k \\ln k\})\}) = \\Theta (\\frac \{k \\ln k\} \{\\ln k\}) = \\Theta (k)$$

3-1  
a. $$P(n) = \\sum\_\{i=0\}^d \{a\_i n^i\} = n^d \\sum\_\{i=0\}^d \{a\_i n^\{i-d\}\} \\le n^d \\sum\_\{i=0\}^d \{a\_i\} \\le cn^k$$ b. $$P(n) = \\sum\_\{i=0\}^d \{a\_i n^i\} \\ge n^d \\ge cn^d$$ c. 由前两问可证。  
d. 同a  
e. 同b

3-2

<table> 
 <tbody> 
  <tr> 
   <td>A</td> 
   <td>B</td> 
   <td>$O$</td> 
   <td>$o$</td> 
   <td>$\Omega$</td> 
   <td>$\omega$</td> 
   <td>$\Theta$</td> 
  </tr> 
  <tr> 
   <td>$\lg^k n$</td> 
   <td>$n^{\epsilon}$</td> 
   <td>yes</td> 
   <td>yes</td> 
   <td>no</td> 
   <td>no</td> 
   <td>no</td> 
  </tr> 
  <tr> 
   <td>$n^k$</td> 
   <td>$c^n$</td> 
   <td>no</td> 
   <td>no</td> 
   <td>yes</td> 
   <td>yes</td> 
   <td>no</td> 
  </tr> 
  <tr> 
   <td>$\sqrt n$</td> 
   <td>$n^{\sin n}$</td> 
   <td>no</td> 
   <td>no</td> 
   <td>no</td> 
   <td>no</td> 
   <td>no</td> 
  </tr> 
  <tr> 
   <td>$2^n$</td> 
   <td>$2^{n/2}$</td> 
   <td>no</td> 
   <td>no</td> 
   <td>yes</td> 
   <td>yes</td> 
   <td>no</td> 
  </tr> 
  <tr> 
   <td>$n^{\lg c}$</td> 
   <td>$c^{\lg n}$</td> 
   <td>yes</td> 
   <td>no</td> 
   <td>yes</td> 
   <td>no</td> 
   <td>yes</td> 
  </tr> 
  <tr> 
   <td>$\lg {(n!)}$</td> 
   <td>$\lg {(n^n)}$</td> 
   <td>yes</td> 
   <td>no</td> 
   <td>yes</td> 
   <td>no</td> 
   <td>yes</td> 
  </tr> 
 </tbody> 
</table>

3-3  
a. $$2^\{2^\{n+1\}\} > 2^\{2^n\} > (n+1)! > n! > e^n > n 2^n > 2^n > (3/2)^n > (\\lg n)^\{\\lg n\} = n^\{\\lg \{\\lg n\}\} > (\\lg n)!$$ $$ > n^3 > n^2 = 4^\{\\lg n\} > n \\lg n= \\lg \{(n!)\} > n = 2^\{\\lg n\} > (\\sqrt 2)^\{\\lg n\} = \\sqrt n > 2^\{\\sqrt \{2\\lg n\}\} > \\lg^2 n > \\ln n$$ $$ > \\sqrt \{\\lg n\} > \\ln \{\\ln n\} > 2^\{\\lg^\* n\} > \\lg^\* n = \\lg^\*\{(\\lg n)\} > \\lg \{(\\lg^\* n)\} > n^\{1/ \\lg n\} = 2 = 1$$ b. 非连续性函数或者震荡函数就能满足要求，比如 $$f(n)=\\cases \{ n, & $-1^n &gt 0$ \\\\ 0, & $\{-1\}^n < 0$ \}$$

3-4  
a. 错误，举个反例$n=O(n^2)$，而$n^2 \\ne O(n)$  
b. 错误，举个反例$n + n^2 = O(n^2) \\ne O(\\min (n, n^2)) = O(n)$  
c. 正确，$f(n)=O(g(n))$表明存在正常数$c, n\_0$对所有$n \\ge n\_0$都有$f(n) \\le c g(n)$，所以也有$\\lg \{f(n)\} \\le \\lg \{(c g(n))\}$，得证  
d. 正确，$f(n)=O(g(n))$表明存在正常数$c, n\_0$对所有$n \\ge n\_0$都有$f(n) \\le c g(n)$，所以也有$2^\{f(n)\} \\le 2^\{c g(n)\}$，得证  
e. 正确，同理可证。  
f. 正确，定义直接证明。  
g. 错误，举个反例$2^n = \\Theta(2^n) = \\omega(2^\{n/2\})$  
h. 正确，$g(n)=o(f(n))$表明存在正常数$n\_0$对于任意正常数$c$，对所有$n \\ge n\_0$都有$g(n) < f(n)$，所以对于所有$n \\ge n\_0$都有$f(n)+o(f(n))) < f(n) + f(n) = 2f(n)$，得证。

3-5  
a. 只要证明$f(n)=O(g(n))$的补集包含于$f(n)=\\overset\{\\infty\}\{\\Omega\} (g(n))$中即可。$f(n)=O(g(n))$表示存在正常数$c, n\_0$对所有$n \\ge n\_0$都有$f(n) \\le c g(n)$，那么他的补集是不存在常数$c, n\_0$对所有$n \\ge n\_0$都有$f(n) \\le c g(n)$，显然包含于$f(n)=\\overset\{\\infty\}\{\\Omega\} (g(n))$中，因为如果存在正常数c对有限个n的话成立的话，就能找到一个$n\_0$大于有限个n中最大的那个，使得$f(n) \\le c g(n)$成立。但是如果换成$\\Omega (g(n))$的话，3-3b中的例子就是个反例。  
b. 用符号$\\Omega (f(n))$可以保证在n足够大的情况下算法复杂度都不低于$f(n)$，即最好的情况下也不低于$f(n)$。而使用符号$\\overset\{\\infty\}\{\\Omega\} (f(n))$则表示该算法在很多时候复杂度都不低于$f(n)$，但在某些比较好的情况下有可能会低于$f(n)$。  
c. 没有变化？求指教  
d. $$\\eqalign \{ \\tilde \\Omega (g(n)) = \\\{ f(n) : & \\exists c,k,n\_0 > 0 对\\,\\forall n \\ge n\_0 \\\\ & 有0 \\le c g(n) \\lg^k(n) \\le f(n)\\\} \}$$ $$\\eqalign \{ \\tilde \\Theta (g(n)) = \\\{ f(n) : & \\exists c\_1,c\_2,k,n\_0 > 0 对\\,\\forall n \\ge n\_0 \\\\ & 有0 \\le c\_1 g(n) \\lg^k(n) \\le f(n) \\le c\_2 g(n) \\lg^k(n) \\\} \}$$ 定理3.1由定义可知。

3-6  
a. $\\Theta (n)$  
b. $\\Theta (\\lg^\* n)$  
c. $\\Theta (\\lg n)$  
d. $\\Theta (\\lg n)$  
e. $\\Theta (\\lg \{\\lg n\})$  
f. $\\infty$  
g. $\\Theta (\\lg \{\\lg n\})$  
h. 不会，求指教

转载于:https://www.cnblogs.com/Jiajun/archive/2013/05/06/3063574.html