算法导论第三章函数的增长

第三章 函数的增长

3.1 渐进记号

$\Theta$记号

$\Theta(g(n))={f(n)$:存在正常量$c_1$、$c_2$和$n_0$，使得对所有$n\geq n_0$，有$0\leq c_1g(n)\leq f(n)\leq c_2g(n)}$

$g(n)$为$f(n)$的渐进紧确界

$O$记号

$O(g(n))={f(n)$：存在正常量$c$和$n_0$，使得对所有$n\geq n_0$，有$0\leq f(n)\leq cg(n)}$

$g(n)$为$f(n)$的渐近上界

$o$记号

$o(g(n))={f(n)$：对任意正常量$c>0$，存在常量$n_0>0$，使得对所有$n\geq n_0，有0\leq f(n)< cg(n)}$

$O$中c对某个正常量成立，$o$中$c$对任意正常量成立

例：$2n=O(n^2)$，$2n^2\neq o(n^2)$

$\Omega$记号

$\Omega(g(n))={f(n)：$存在正常量$c$和$n_0$，使得对所有$n\geq n_0$，有$0\leq cg(n)\leq f(n)}$

$g(n)$为$f(n)$的渐进下界

$\omega$记号

$\omega(g(n))={f(n)：对任意正常量c>0，存在常量n_0>0，使得对所有n\geq n_0，有0\leq cg(n)<f(n)}$

例：$\frac{n^2}{2}=\omega(n)$，$\frac{n^2}{2}\neq \omega(n^2)$

传递性

$$\begin{align} &f(n)=\Theta(g(n))&\&\ \ &g(n)=\Theta(h(n))\ \ \ \ &\Rightarrow\ \ \ \ &f(n)=\Theta(h(n))\\ &f(n)=O(g(n))&\&\ \ &g(n)=O(h(n))\ \ \ \ &\Rightarrow\ \ \ \ &f(n)=O(h(n))\\ &f(n)=\Omega(g(n))&\&\ \ &g(n)=\Omega(h(n))\ \ \ \ &\Rightarrow\ \ \ \ &f(n)=\Omega(h(n))\\ &f(n)=\omicron(g(n))&\&\ \ &g(n)=\omicron(h(n))\ \ \ &\Rightarrow\ \ \ \ &f(n)=\omicron(h(n))\\ &f(n)=\omega(g(n))&\&\ \ &g(n)=\omega(h(n))\ \ \ \ &\Rightarrow\ \ \ \ &f(n)=\omega(h(n))\\ \end{align}$$

自反性

$$\begin{align} &f(n)=\Theta(f(n))\\ &f(n)=O(f(n))\\ &f(n)=\Omega(f(n)) \end{align}$$

对称性

$$f(n)=\Theta(g(n))\ \ \ \ 当且仅当\ \ \ \ g(n)=\Theta(f(n))$$

转置对称性

$$\begin{align} f(n)=O(g(n))\ \ \ \ &当且仅当\ \ \ \ g(n)=\Omega(f(n))\\ f(n)=\omicron(g(n))\ \ \ \ &当且仅当\ \ \ \ g(n)=\omega(f(n)) \end{align}$$

3.1-1

对于渐进非负函数$f(n)$和$g(n)$，可以得到:

$f(n)>0,g(n)>0$

$max{f(n),g(n)}<2(f(n)+g(n))$

$f(n)\le max{f(n),g(n)}$

$g(n)\le max{f(n),g(n)}$

$\frac12(f(n)+g(n))\le max{f(n),g(n)}$

所以，存在$c_1=0.5,c_2=2$，使得$c_1(f(n)+g(n))\le max{f(n),g(n)}\le c_2(f(n)+g(n))$，问题得证。

3.1-2

$$\begin{align} n+a&\leq n+|a| \\ &\leq 2n,\ \ \ \ |a|\leq n\\ n+a&\geq n-|a|\\ &\geq \frac12n,\ \ \ \ |a|\leq\frac12n \end{align}$$

则，$n\geq 2|a|$时

$0\leq \frac12n\leq n+a\leq 2n$

$b>0$

$0\leq (\frac12n)^b\leq (n+a)^b\leq (2n)^b$

$0\leq (\frac12)^bn^b\leq (n+a)^b\leq 2^bn^b$

所以，对任意a和b，都存在$c_1=(\frac12)^b,c_2=2^b,n_0>2|a|$，满足$(n+a)^b=\Theta(n^b)$

3.1-3

设运行时间为T(n)，$T(n)>O(n^2)$表示T(n)>f(n)，f(n)为满足$O(n^2)$的某些函数。对g(n)=0，所有n均对$O(n^2)$成立，这条公式对所有运行时间T(n)成立，得出运行时间总是非负的。所以，这一表述无意义。

3.1-4

对$2^{n+1}=O(2^n)$，设$f(n)=2^{n+1}=2\times 2^n$，满足$0\leq 2\times 2^n\leq 2\times2^n$，对所有n成立，所以$2^{n+1}=O(2^n)$成立。

对$2^{2n}=O(2^n)$，设$f(n)=2^{2n}=2^n\times 2^n$，若要满足$f(n)=O(2^n)$，既满足存在$n>n_0$，$0\leq f(n)\leq c2^n$，易得，若$c=2^{n_0}$，存在$n>n_0$，$f(n)>c2^n$。所以不存在c满足此式，即此式不成立。

3.1-5

$f(n)=\Theta(g(n))\Rightarrow0\leq c_1g(n)\leq f(n)\leq c_2g(n)$

则，f(n)必须满足

1.$0\leq c_1g(n)\leq f(n)$，即$f(n)=\Omega(g(n))$

2.$0\leq f(n)\leq c_2g(n)$，即$f(n)=O(g(n))$

定理3.1得证。

3.1-6

若$f(n)=\Theta(g(n))$，
则$f(n){min}\geq c_1g(n)\geq 0$，
即$f(n)=\Omega(g(n))$，
$f(n){max}\leq c_2g(n)$，
即$f(n)=O(g(n))$。
即最坏情况运行时间为$O(g(n))$，
最好情况运行时间为$\Omega(g(n))$。

3.1-7

设$f(n)=\omicron(g(n))$，$对任意正常量c_1>0，存在常量n_1>0，使得对所有n\geq n_1，有0\leq f(n)< c_1g(n)$

设$f(n)=\omega(g(n))$，$对任意正常量c_2>0，存在常量n_2>0，使得对所有n\geq n_2，有0\leq c_2g(n)<f(n) $

即，当n足够大时，f(n)需满足$f(n)c_2g(n))$。易得，不存在此类f(n)，问题得证。

3.1-8

$$O(g(n,m))=\{f(n,m):存在正常量c、n_0、m_0，使得对所有n\geq n_0或m\geq m_0，\\有0\leq f(n,m)\leq cg(n,m)\}$$ $$\Omega(g(n,m))=\{f(n,m):存在正常量c、n_0、m_0，使得对所有n\geq n_0或m\geq m_0，\\有0\leq cg(n,m)\leq f(n,m)\}$$ $$\Theta(g(n,m))=\{f(n,m):存在正常量c_1、c_2、n_0、m_0，使得对所有n\geq n_0或m\geq m_0，\\有0\leq c_1g(n,m)\leq f(n,m)\leq c_2g(n,m)\}$$

3.2 标准记号与常用函数

单调性

向下取整与向上取整

模运算

多项式

指数

对数

阶乘

多重函数

多重对数函数

斐波那契数

3.2-1

因为$f(n),g(n)$单调递增，所以$n<m$时,

$f(n)<f(m),g(n)<g(m)$，所以$f(n)+g(n)<f(m)+g(m)$

$g(n)<g(m)$，所以$f(g(n))<f(g(m))$

因为$f(n),g(n)$非负，所以

$f(n)\times g(n)<f(m)\times g(n)<f(m)\times g(m)$

3.2-2

$a^{log_bc}=c^{log_ba}$

左边可做变形：

$$\begin{align} a^{log_bc}&=a^{\frac{log_ac}{log_ab} }\\ &=a^{log_ac\cdot log_ba}\\ &=c^{log_ba} \end{align}$$

等式得证

3.2-3

$n!=\sqrt{2\pi n}(\frac ne)^n$

$$\begin{align} lg(n!)&=lg(\sqrt{2\pi n}(\frac ne)^n)\\ &=lg\sqrt{2\pi n}+lg(\frac ne)^n\\ &=nlgn+\frac12lg2\pi+\frac12lgn-nlge \end{align}$$

忽略常数项与低阶项，$lg(n!)=\Theta(nlgn)$，等式(3.19)得证。

对$n!$与$2^n$取对数，得$\Theta(nlgn)$与$\Theta(n)$，易得，$nlgn=\omega(n)$，由传递性，$lg(n!)=\omega(n)$，所以$n!=\omega{2^n}$。

易得，当$n\geq2$时，$n!=n(n-1)(n-2)…\cdot1<n^n=n\cdot n\cdot…\cdot n$，所以$n!=\omicron(n^n)$。

3.2-4

$\lceil{lgn}\rceil=\Theta(lgn)$

$lg(n!)=\Theta(nlgn)$

要证明f(n)是多项式有界的，即要证明存在$c$、$k$、$n_0$使得当$n\geq n_0$时，$f(n)\leq cn^k$，即要证明$lgf(n)\leq cklgn$，即$lgf(n)=O(lgn)$。

$$\begin{align} lg(\lceil lgn\rceil !)&=\Theta(\lceil lgn\rceil lg\lceil lgn\rceil)\\ &=\Theta(lgnlglgn)\\ &=\omega(lgn) \end{align}$$

所以，$lg(\lceil lgn\rceil!)\ne O(lgn)$，$\lceil lgn\rceil!$不是多项式有界的。

$$\begin{align} lg(\lceil lglgn\rceil!)&=\Theta(\lceil lglgn\rceil lg(\lceil lglgn\rceil))\\ &=\Theta(lglgnlglglgn)\\ &=\omicron((lglgn)^2)\\ &=\omicron(lg^2(lgn))\\ &=\omicron(lgn) \end{align}$$

对倒数第二步，$lg^bn=\omicron(n^a)$。

3.2-5

令$lg^n=x$，由$lg^n$的定义，可以得到

$lg^(lgn)=lg^n-1=x-1$

$lg(lg^*n)=lgx$

第二个渐进更大

3.2-6

黄金分割率$\phi$及其共轭数$\hat\phi$是方程$x^2=x+1$的两个根，所以满足该方程。

3.2-7

易得，当$i=0,1$时该等式成立。

当$i\geq2$时，

$$\begin{align} F_i&=F_{i-1}+F_{i-2}\\ &=\frac{\phi^{i-1}-\hat\phi^{i-1} }{\sqrt5}+\frac{\phi^{i-2}-\hat\phi^{i-2} }{\sqrt5}\\ &=\frac{\phi^{i-2}(1+\phi)-\hat\phi^{i-2}(1+\hat\phi) }{\sqrt5}\\ 1+\phi&=\frac{1+\sqrt5}{2}+1\\ &=\frac{3+\sqrt5}{2}\\ \phi^2&=(\frac{1+\sqrt5}2)^2\\ &=\frac{3+\sqrt5}2 \end{align}$$

得$1+\phi=\phi^2$，同理，可得$1+\hat\phi=\hat\phi^2$。

所以

$$\begin{align} F_i&=\frac{\phi^{i-2}(1+\phi)-\hat\phi^{i-2}(1+\hat\phi) }{\sqrt5}\\ &=\frac{\phi^{i-2}\phi^2-\hat\phi^{i-2}\hat\phi^2 }{\sqrt5}\\ &=\frac{\phi^i-\hat\phi^i}{\sqrt5} \end{align}$$

等式成立。

3.2-8

因为$klnk=\Theta(n)$，所以存在正常量$c_1$、$c_2$和$n_0$，使得对所有$n\geq n_0$，有$0\leq c_1n\leq klnk\leq c_2n$

则同理，存在正常量$c_1$、$c_2$，对所有$n\geq n_0$，有$0\leq \frac{1}{c_2}klnk\leq n\leq \frac{1}{c_1}klnk$。

所以$n=\Theta(klnk)$，即$k=\Theta(nlnn)$。

问题得证。

章末思考题

3-1多项式的渐进行为

假设$p(n)=\sum_{i=0}^da_in^i$是一个关于$n$的$d$次多项式，其中$a_d>0$，$k$是一个常量。使用渐进记号的定义来证明下面的性质。

a.若$k\ge d$，则$p(n)=O(n^k)$。

b.若$k\le d$，则$p(n)=\Omega(n^k)$。

c.若$k=d$，则$p(n)=\Theta(n^k)$。

d.若$k>d$，则$p(n)=o(n^k)$。

e.若$k<d$，则$p(n)=\omega(n^k)$。

根据极限和渐进记号的定义，可以证明以上5个命题。

3-2相对渐进增长

为下表中的每对表达式$(A,B)$指出$A$是否是$B$的$O$、$o$、$\Omega$、$\omega$或$\Theta$。假设$k\ge1$、$\varepsilon>0$且$c>1$均为常量。

A	B	$O$	$o$	$\Omega$	$\omega$	$\Theta$
$lg^kn$	$n^\varepsilon$	否	否	是	是	是
$n^k$	$c^n$	否	否	是	是	否
$\sqrt{n}$	$n^{sinn}$	否	否	否	否	否
$2^n$	$2^{n/2}$	是	是	否	否	否
$n^{lgc}$	$c^{lgn}$	是	否	是	否	是
$lg(n!)$	$lg(n^n)$	是	否	是	否	是

备注：a. 根据$k$和$\varepsilon$取值不同而不同

​ 对于题意，以b.为例，$B=\Omega(A)$。

3-3根据渐进增长率排序

a.根据增长的阶来排序下面的函数，即求出满足$g1=\Omega(g_2)$，$g_2=\Omega(g_3)$，……，$g{29}=\Omega(g{30})$的函数的一种排列$g_1$，$g_2$，……，$g{30}$。把你的表划分成等价类，使得函数$f(n)$和$g(n)$再相同类中当且仅当$f(n)=\Theta(g(n))$。

快
	$2^{lg^*n}$
?	$lg^*(lgn)$	$lg^*n$
	$lg(lg^{*}n)$
	$1$	$n^{\frac{1}{lgn}}=2$
慢