\(\because\)f(n)与g(n)为渐进非负函数
\(\therefore \exists n_0\)，当n>\(n_0\)时，
\(0\leq f(n)\leq max(f(n),g(n)), 0\leq g(n)\leq max(f(n),g(n))\)
两式相加，得\(0\leq (f(n)+g(n))/2\leq max(f(n),g(n))\)
而\(max(f(n),g(n))\leq f(n)+g(n))\)
\(\therefore 0\leq (f(n)+g(n))/2\leq max(f(n),g(n))\leq f(n)+g(n)\)
根据定义有 max(f(n),g(n)) = \(\Theta (f(n)+g(n))\)
根据定义，要使得f(n) = \(\Theta (g(n))\)
需要\(\exists c_1,c_2,n_0\)使得对于所有 \(n\geq n_0\)，有\(0\leq c_1g(n)\leq f(n) \leq c_2g(n)\)
要使得\(f(n) = O(g(n)), f(n) = \Omega(g(n))\)，分别有
\(\exists c3,n_1\)使得对于所有\(n\geq n_1\)，有 \(f(n)\leq c_3f(n)\)
\(\exists c4,n_2\)使得对于所有\(n\geq n_2\)，有 \(f(n)\leq c_4f(n)\)
若\(f(n) = O(g(n)), f(n) = \Omega(g(n))\)同时满足
当\(n\geq max(n_1,n_2)\)时，有\(0\leq c_4g(n)\leq f(n) \leq c_3g(n)\)
根据定义，有f(n) = \(\Theta (g(n))\)
若$f(n) = \(\Theta (g(n))\)
当\(n\geq n_0\)时，有 \(0\leq c_1g(n)\leq f(n)\leq c_2g(n)\)
即\(0\leq c_1g(n)\leq f(n), f(n)\leq c_2g(n)\)
根据定义，有f(n) = O(g(n)) 且 f(n) = \(\Omega (g(n))\)
\(lim_{n->\infty }\frac{p(n)}{n^k} = lim_{n->\infty }\frac{\sum^d_{i=0}a_in^i}{n^k} = lim_{n->\infty }\frac{d!a_d}{n^k} = 0\)
\(\therefore \exists n_0,\) 当\(n>n_0\)时，对于任意c>0，有\(cn^k>\sum ^d_{i=0}a_in^i\)
根据定义，有\(p(n) = o(n^k)\)
| 序号 | A | B | O | o | \(\Omega\) | \(\omega\) | \(\Theta\) |
|---|---|---|---|---|---|---|---|
| a. | \(lg^kn\) | \(n^\varepsilon\) | x | x | o | o | x |
| b. | \(n^k\) | c^n | x | x | o | o | x |
| c. | \(\sqrt{n}\) | \(c^n\) | x | x | x | x | x |
| d. | \(2^n\) | \(2^{n/2}\) | o | o | x | x | x |
| e. | \(n^{lgc}\) | \(c^{lgn}\) | o | x | o | x | o |
| f. | lg(n!) | \(lg(n^n)\) | o | x | o | x | o |
a,b,c,d显然
\(lim_{n->\infty}\frac{ n^{lgc} }{ c^{lgn} }\)
=\(lim_{n->\infty}\frac{n^{log_nc/log_n10}}{c^{lgn}}\)
=\(lim_{n->\infty}\frac{n^{1/log_n10}}{c^{lgn}}\)
= 1
所以 \(n^{lgc} = \Theta(c^{lgn})\)
原文：https://www.cnblogs.com/baoliang/p/12123140.html