渐进分析的一些例子

摘要: 渐进分析的一些经典问题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

在文章 函数增长与渐进分析入门 中我们学习了函数增长的阶和渐进分析的一些基础知识。本文我们看一些渐进分析中的一些经典问题。

多项式的渐进行为

考虑多项式 $p(n) = \sum\limits_{i=0}\limits^{d}a_{i}n^{i}$ 是一个关于 $n$ 的 $d$ 次多项式，其中 $a_{d} > 0$，$k$ 是一个常量。则有下面的性质：

• 若 $k \geq d$，则 $p(n) = O(n^{k})$
• 若 $k \leq d$，则 $p(n) = \Omega(n^{k})$
• 若 $k = d$，则 $p(n) = \Theta(n^{k})$
• 若 $k > d$，则 $p(n) = o(n^{k})$
• 若 $k < d$，则 $p(n) = \omega(n^{k})$

以 $p(n) = O(n^{d})$ 为例，我们看一下推导过程。首先回顾一下 $O$ 记号的定义：

使用 $O$ 记号给出了函数的渐进上界。对于给定函数 $g(n)$，$O(g(n))$ 表示以下函数的集合：

$$O(g(n)) = \{f(n):\exists c, n_{0}>0，使得 \forall n \geq n_{0}，有 0 \leq f(n) \leq cg(n)\}$$

若要证 $p(n) = O(n^{d})$，按照定义，也就是要取到一个 $c$ 和 $n_{0}$，使得 $n \geq n_{0}$ 时，有：

$$\begin{align} p(n) &= \sum\limits_{i=0}\limits^{d}a_{i}n^{i} \\ &= a_{d}n^{d} + a_{d-1}n^{d-1} + \cdots + a_{1}n + a_{0} \\ &\leq cn^{d} \end{align}$$

也就是：

$$c \geq a_{d} + \frac{a_{d-1}}{n} + \frac{a_{d-2}}{n^{2}} + \cdots + \frac{a_{0}}{n^{d}}$$

记 $c = a_{d} + b$，于是上式可以写为：

$$b \geq \frac{a_{d-1}}{n} + \frac{a_{d-2}}{n^{2}} + \cdots + \frac{a_{0}}{n^{d}}$$

取 $b = 1$，如果能找到一个 $n_{0}$，使得 $n \geq n_{0}$ 时，上式成立，则 $p(n) = O(n^{d})$ 得证。

下面取 $n_{0}$ 为以下值：

$$n_{0} = \max(da_{d-1}, d\sqrt{a_{d-2}}, \cdots, da_{0}^{\frac{1}{d}})$$

此时即有：

$$p(n) \leq cn^{d} \quad (n \geq n_{0})$$

这正是 $p(n) = O(n^{d})$ 的定义。

相对渐进增长

下面是一些对比两个函数渐进增长率的例子，其中 $k \geq 1$，$\epsilon > 0$，$c > 1$。

若 $A = Symbol(B)$ 则在对应的格子中记 yes，否则记 no，其中 Symbol 为 $O, o, \Omega, \omega, \Theta$ 之一。

A	B	$O$	$o$	$\Omega$	$\omega$	$\Theta$
$\log^{k}n$	$n^{\epsilon}$	yes	yes	no	no	no
$n^{k}$	$c^{n}$	yes	yes	no	no	no
$\sqrt{n}$	$n^{\sin{n}}$	no	no	no	no	no
$2^{n}$	$2^{n/2}$	no	no	yes	yes	no
$n^{\log c}$	$c^{\log n}$	yes	no	yes	no	yes
$\log(n!)$	$\log(n^{n})$	yes	no	yes	no	yes

按渐进增长率排序

下面是一些按照增长的阶来排序的函数的例子，从上到下对应函数增长的阶从大到小。

记第 $i$ 行的函数为 $g_{i}$，有 $g_{i} = \Omega(g_{i+1})$：

$$2^{2^{n+1}} \\ 2^{2^{n}} \\ (n+1)! \\ n! \\ e^{n} \\ n2^{n} \\ 2^{n} \\ (\frac{3}{2})^{n} \\ (\log n)^{\log n}, n^{\log\log n} \\ (\log n)! \\ n^{3} \\ n^{2}, 4^{\log n} \\ n\log n, \log(n!) \\ n, 2^{\log n} \\ \sqrt{n}, (\sqrt{2})^{\log n} \\ 2^{\sqrt{2\log n}} \\ \log^{2}n \\ \ln n \\ \sqrt{\log n} \\ \ln\ln n \\ 2^{\log^{* }n} \\ \log^{* } n, \log^{* }(\log n) \\ \log(\log^{* }n) \\ n^{\frac{1}{\log n}}, 1 \\$$

我们也可以举出函数 $g(n)$，使得对以上的任意函数 $g_{i}$，$f(n)$ 既不是 $O(g_{i}(n))$ 也不是 $\Omega(g_{i}(n))$：

$$f(n) = \left\{ \begin{array}{**lr**} 2^{2^{n+2}} \quad n 为偶数 \\ 0 \quad n 为奇数 \\ \end{array} \right.$$

渐进记号的一些性质

下面是一些渐进记号的性质：

(1) $f(n) = O(g(n)) \Rightarrow \log(f(n)) = O(\log(g(n)))$，其中对足够大的 $n$，有 $\log(g(n)) \geq 1$，且 $f(n) \geq 1$。

由 $f(n) \geq 1, f(n) = O(g(n))$，有：

$$\exists c, n_{0}: \forall n \geq n_{0}, 0 \leq f(n) \leq cg(n)$$

于是有：

$$0 \leq \log f(n) \leq \log(cg(n)) = \log c + \log g(n)$$

按照 $log(f(n)) = O(\log(g(n)))$ 的定义，我们要证明 $\log f(n) \leq d\log g(n)$，$d$ 取以下值即可：

$$d = \frac{\log c + \log g(n)}{\log g(n)} = \frac{\log c}{\log g(n)} + 1 \leq \log c + 1$$

(2) $f(n) = O((f(n))^{2})$，其中 $f(n) \geq 1$

当 $f(n) \geq 1$，有 $0 \leq f(n) \leq cf^{2}(n)$。

(3) $f(n) = O(g(n)) \Rightarrow g(n) = \Omega(f(n))$

由 $0 \leq f(n) \leq cg(n)$，取 $d = \frac{1}{c}$ 即可得 $0 \leq df(n) \leq g(n)$。

(4) $f(n) + o(f(n)) = \Theta(f(n))$

令 $g(n) = o(f(n))$，于是：

$$\exists c, n_{0}: \forall n \geq n_{0}, 0 \leq g(n) \leq cf(n)$$

我们要证明的是：

$$\exists c_{1}, c_{2}, n_{0}: \forall n \geq n_{0}, 0 \leq c_{1}f(n) \leq f(n) + g(n) \leq c_{2}f(n)$$

取 $c_{1} = 1, c_{2} = c + 1$ 即可。

渐进记号的一些错误命题

下面是两个错误命题，我们给出反例：

(1) $f(n) = O(g(n)) \Rightarrow 2^{f(n)} = O(2^{g(n)})$

令 $f(n) = 2n, g(n) = n$，满足 $2n = O(n)$，但是 $2^{2n} = 4^{n} \neq O(2^{n})$

(2) $f(n) = \Theta(f(\frac{n}{2}))$

令 $f(n) = 2^{n}$，我们要证明：

$$\exists c_{1}, c_{2}, n_{0}: \forall n \geq n_{0}, 0 \leq c_{1}2^{n/2} \leq 2^{n} \leq c_{2}2^{n/2}$$

而上式是不成立的。

多重函数的渐进分析

回顾多重函数的定义。用记号 $f^{(i)}(n)$ 表示函数 $f(n)$ 重复 i 次作用于一个初值 n 上。$f(n)$ 为实数集上的一个函数，对非负整数 i，递归定义：

$$f^{(i)}(n) = \left\{ \begin{array}{**lr**} \begin{align} & n & i = 0 \\ & f(f^{(i-1)}(n)) & i > 0 \\ \end{align} \end{array} \right.$$

对给定的常数 $c$，定义 $f_{c}^{*}$：

$$f_{c}^{* }(n) = \min\{i \geq 0: f^{(i)}(n) \leq c\}$$

对于下面一些 $f(n)$ 和 $c$ 的例子，我们给出 $f_{c}^{*}(n)$ 的尽量紧确的界：

$f(n)$	$c$	$f_{c}^{*}(n)$
$n - 1$	0	$\Theta(n)$
$\log n$	1	$\Theta(\log^{* }n)$
$n / 2$	1	$\Theta(\log n)$
$n / 2$	2	$\Theta(\log n)$
$\sqrt{n}$	1	$\Theta(\log\log n)$
$\sqrt{n}$	2	不收敛
$n^{1/3}$	2	$\Theta(\log_{3}\log n)$
$n/\log n$	2	$\omega(\log\log n)$, $o(\log n)$

---