算法分析中的渐近记号总结

最近在看算导决定抽空把算法基础在夯实一遍, 算法相关的实现代码时不时会丢到GitHub上，主要以C++实现，也会有相应的Python和Javascript的实现。

在这里，作为算法的渐近分析的标准方法之一，对几种渐近记号进行下总结.

渐近记号

所有的渐近记号都表示一个函数的集合.

$\Theta$ 记号

$\Theta$ 记号表示一个函数的渐近紧确界，同时包含了渐近上界和渐近下界。

通常对于$\Theta$ 的一种非形式化的概念，我们通过去掉低阶项并忽略最高项的系数来获取其紧确界的函数形式。

来看下他的严格定义, 对于一个给定的函数$g(n)$, 我们用$\Theta(g(n))$ 表示这样的一个函数集合:

$\Theta(g(n)) = \{f(n):$ 存在正常量 $c_{1}$、 $c_{2}$ 和 $n_{0}$, 使得对所有 $n > n_{0}$, 有 $0 \leq c_{1}g(n) \leq f(n) \leq c_{2}g(n)\}$

$O$ 记号

$O$ 记号是一个比 $\Theta$ 记号更弱的概念，他只表示一个函数的渐近上界, 也就是最坏的运行时间。

对于一个给定的函数$g(n)$, 我们用$O(g(n))$ 表示这样的一个函数集合:

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

有时候$O$记号非形式化的表示一个函数的渐近紧确界，也就是$\Theta$记号表示的集合, 这也是为什么有时候看到$n = O(n^{2})$会感觉不对.

$\Omega$ 记号

类似 $O$ 记号，$\Omega$ 记号表示的是一个函数的渐近下界，也就是最好的运行时间

对于一个给定的函数$g(n)$, 我们用$\Omega(g(n))$ 表示这样的一个函数集合:

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

$o$ 记号

$O$ 记号表示的是一个函数的渐近上界，但是可能是渐近紧确界也可能不是，例如$3n^{2} = O(n^{2})$ 中 $O$ 表示的就是紧确上界，而 $n = O(n^{2})$ 中的 $O(n^{2})$ 便不是紧确上界. $o$ 记号就表示非紧确界的情况, 即 $2n = o(n^{2})$ 但是 $2n^{2} \neq o(n^{2})$

写下定义吧, 对于一个给定的函数 $g(n)$, 我们用 $o(g(n))$ 表示这样一个函数集合:

$o(g(n)) = \{f(n):$ 对任意常量 $c > 0$, 存在常量 $n_{0}$, 使得对所有 $n \geq n_{0}$, 有 $0 \leq f(n) \leq cg(n)\}$

直观上来看，在 $o$ 记号中, 当 $n$ 趋近于无穷大时， 函数 $f(n)$ 的值会远小于 $g(n)$ 的值, 即

$${\lim_{x \to \infty}} \frac{f(n)}{g(n)} = 0$$

$\omega$ 记号

类似 $o$ 与 $O$ 的关系类似, $\omega$ 记号用来表示一个非渐近紧确下界。 它的定义:

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

类似 $o$ 记号， $\omega$ 记号也有

$${\lim_{x \to \infty}} \frac{g(n)}{f(n)} = 0$$

渐近记号的比较

假定 $f(n)$ 和 $g(n)$ 都渐近为正.

传递性

  • $f(n) = \Theta(g(n))$ 且 $g(n) = \Theta(h(n))$ 则 $f(n) = \Theta(h(n))$
  • $f(n) = O(g(n))$ 且 $g(n) = O(h(n))$ 则 $f(n) = O(h(n))$
  • $f(n) = \Omega(g(n))$ 且 $g(n) = \Omega(h(n))$ 则 $f(n) = \Omega(h(n))$
  • $f(n) = o(g(n))$ 且 $g(n) = o(h(n))$ 则 $f(n) = o(h(n))$
  • $f(n) = \omega(g(n))$ 且 $g(n) = \omega(h(n))$ 则 $f(n) = \omega(h(n))$

自反性

  • $f(n) = \Theta(f(n))$
  • $f(n) = O(f(n))$
  • $f(n) = \Omega(f(n))$

对称性

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

转置对称性

  • $f(n) = O(g(n))$ 当且仅当 $g(n) = \Omega(f(n))$
  • $f(n) = o(g(n))$ 当且仅当 $g(n) = \omega(f(n))$

渐近比较和实数比较的类比

  • $f(n) = \Theta(g(n))$ 类似于 $a = b$, $f(n)$ 渐近等于 $g(n)$
  • $f(n) = O(g(n))$ 类似于 $a \leq b$, $f(n)$ 渐近小于等于 $g(n)$
  • $f(n) = \Omega(g(n))$ 类似于 $a \geq b$, $f(n)$ 渐近大于等于 $g(n)$
  • $f(n) = o(g(n))$ 类似于 $a < b$, $f(n)$ 渐近小于 $g(n)$
  • $f(n) = \omega(g(n))$ 类似于 $a > b$, $f(n)$ 渐近大于 $g(n)$

三分性 不一定成立

对于值会来回摆动的函数三分性便不成立，例如:

$n^{1+sin(n)} \neq O(n)$ 且 $n^{1+sin(n)} \neq \Omega(n)$

Comments

▲