Day-5 演算法分析工具 : 渐进式符号(Big-O, Big-Theta, Big-Omega)

前言

比较合并排序法与插入排序法，一旦输入n的规模足够大时，合并排序在最坏情况所需的时间Θ $(nlgn)$ ，而插入排序法在最坏情况所需的时间为Θ $(n^2)$ ，当n足够大时，合并排序法的效率远远超过插入排序法。对於足够大的输入，一个演算法所需的时间受到最高次项的影响要远远超过低次项与常数项，因此，在输入够大的情况会将其忽略。

当输入够大时，演算法所需的时间只和增加的量级有关，我们通常只关心演算法的渐进效率(asymptotic efficiency)。所谓渐进效率，即是当输入的数量够多时，演算法所需的时间和输入的数量呈现怎样的关系，是呈现线性关系，还是指数关系等等。

演算法常见的估计方法，渐进式符号(Asymptotic Notation)

用来描述演算法渐进运行时间的渐进式符号是以一个定义域为自然数集合 $N$ = { $0,1,2,....$ }的函数来定义。而这样定义函数的定义域有助於我们在处理最坏的情况，当然，我们也可以按照渐进符号的使用情况，让这些符号的定义域在任意集合，如实数域等等集合。

前面我们写到插入排序法的最差情况为Θ $(n^2)$ ，使用Θ这个渐进符号来描述演算法所需要的时间。而Θ $(n^2)$ 这样的表示法，是由我们推导出来的 $an^2+bn+c$ 所写出来的，其中 $a,b,c$ 这些皆为常数，通过写成，渐进符号通常应用在函数或是多项式上。

渐进式分析是基於以下几个观点

忽略掉关於电脑运行速度的因素，那些因素会以常数符号c作为替代
不关心一个演算法的运行时间，而是关心他的增长量，也就是输入规模n趋近於无限时。

所谓的渐进式符号，为描述演算法趋势的一个函数集合。

Θ

给定一个函数 $g(n)$ ，使用Θ $(g(n))$ 来表示以下函数的集合:

Θ $(g(n))$ = { $f(n):$ 存在正实数 $c_1, c_2$ 和 $n_0$ 使得对所有 $n >= n_0$ ，有 $0 <= c_1g(n) <= f(n) <= c_2g(n)$ }
如果存在正整数 $c_1,c_2$ ，使得对於足够大的n， $f(x)$ 能够被 $c_1g(n)$ 和 $c_2g(n)$ 之间，我们就可以说 $f(x)$ 是属於Θ $(g(n))$ 这个函数集合中。
我们具体的证明 $1/2n^2-3n=$ Θ $(n^2)$ 这个式子，令 $c_1,c_2,n_0$ 属於正整数集合，使得对所有 $n>=n_0$ ，有
$c_1n^2<=1/2n^2-3n<=c_2n^2$ ，把 $n^2$ 除掉，得到
$c_1<=1/2-3/n<=c_2$
得到选择任意 $c_2>=1/2$ ，可以使得 $1/2-3/n$ 对於任意 $n>=1$ 的值成立，而对於 $c_1<=1/14$ ，可以使 $1/2-3/n$ 对於任意 $n>=7$ 成立。因此，当 $c_1=1/14, c_2=1/2$ 且 $n_0=7$ ，可以证明 $1/2n^2-3n=$ Θ $(n^2)$ 。当然，对於其他一些常数也是如此，重点是存在某一个常数，可以被包含在Θ $(n^2)$ 这个函数集合中。

简单来说，一个式子忽略掉常数和低阶项，举例: $3n^3 + 90n^2 - 5n + 6789 =$ Θ $(n^3)$ (注意: θ是大写)，他所表示的概念是大於等於并且小於等於。

以集合的观点看待，Θ $(g(n))$ = O $(g(n))$ ∩Ω $(g(n))$

一般情况，会以 $f(n) =$ Θ $(g(n))$ 描述这样的观念，这里的'='不是'等於'的意思，而是'属於'的意思

在上图我们可以看到函数 $c_1g(n)$ 和 $c_2g(n)$ 将函数 $f(n)$ 夹在中间。看到图形的x轴，我们可以看到当 $n_0$ 往n的方向逼近， $f(n)$ 的值是高於 $c_1g(n)$ 但低於 $c_2g(n)$ 的，换句话说，对所有 $n>=n_0$ ，函数 $f(n)$ 必然在n到 $n_0$ 的范围中，找到一个k使得 $f(k) = g(n)$ ，这时候我们会称 $g(n)$ 是 $f(n)$ 的一个渐进临界线(asymptotically tight bound)。

Big-O

如果存在一个正实数c和 $n_0$ 使得当 $N >= n_0$ 时 $T(N) <= cf(N)$ ,则表示为 $T(N) = O(f(N))$ ，通常用於评估一个演算法最久要花费多少时间，也就是一个演算法的上限，小於等於的概念，一个演算法至少会小於等於Big-O函数集合的概念。

另一种Big-O定义方式 : 假设存在两常数 $c > 0, n_0 > 0$ ，使得 $0 <= f(n) <= cg(n)$ ，对於所有 $n >= n_0$ 皆成立，值得注意的一点为Big-O为非对称符号(asymmetric)，A = B不代表B = A。
以集合观点来定义Big-O， $f(n)$ 属於 $g(n)$ 的子集，集合中的元素皆为函数，我们可以定义 $O(g(N)) =$ { $f(n) :$ 为一个函数集合，存在 $c > 0, n_0 > 0$ ，使得 $f(n)$ 以0和 $cg(n)$ 为界， $0 <= f(n) <= cg(n)$ ，对所有 $n>= n_0$ 皆成立 }，也就是 $f(n)$ 的渐进成长率小於 $g(n)$

另外一个集合的观点，我们可以发现 $f(n)=$ Θ $(g(n))$ 这个观念中，其实蕴含 $f(n) = O(g(n))$ 这个概念。

Example 1 : $2n^2 = O(n^3)$ ， $2n^2$ 小於或是等於 $n^3$ ，根据上面的定义，我们不能说 $2n^2$ 等於 $O(n^3)$ ，我们只能说 $2n^2$ 是属於 $O(n^3)$ 的子集。因此这里的等号需要理解成属於某个集合的概念，更精确的写法，也可以写 $2n^2$ ∈ $O(n^3)$ 。

Example 2 : $f(n) = n^3 + O(n^2)$ ，表示存在一个函数 $h(n)$ ∈ $O(n^2)$ 使得 $f(n) = n^3 + h(n)$

Example 3 : $n^2 + O(n) = O(n^3)$ ，对所有函数 $f(n)$ ∈ $O(n)$ ，存在 $h(n)$ ∈ $O(n^2)$ ，使得 $n^2 + f(n) = h(n)$

Ω

如果存在一个正实数c和 $n_0$ 使得当 $N >= n_0$ 时 $T(N) >= cg(N)$ ,则表示为 $T(N) =$ Ω $(g(N))$ ，表是一个演算法的下界，也就是最好的情况，花最少时间的时候，大於等於的概念，一个演算法至少会大於等於Ω。

- 以集合的观点进行定义，Ω $(g(n)) =$ { $f(n):$ 存在常数 $c > 0, n_0 > 0$ 使得 $0 <= cg(n) <= f(n)$ 对所有 $n >= n_0$ }

Example 1 : √ $n$ = Ω $(lgn)$ 概念上为当n足够大时，√ $n$ 总是大於等於Ω $(lgn)$

Little-o

我们上面介绍到Big-O这个渐进符号，但是我们可以发现到Big-O所提供的渐进情况可能不是精确的，像是 $2n^2=O(n^2)$ ，这个使用Big-O的确是精确的上界，但是 $2n=O(n^2)$ ，虽然是函数的上界，但却不是精确的。我们这里使用little-o来表示一个非渐进式的精确上界。

$o(g(n)) =$ { $f(n)$ 对於任一正整数 $c>0$ ，存在常数 $n_0>0$ ，使得对所有 $n>=n_0$ ，有 $0<=f(n)<cg(n)$ }
概念上就是 $f(n)$ 函数的增长率严格小於 $g(n)$

Example 1 : $2n=o(n^2)$ ，但是 $2n^2!=o(n^2)$

比较Big-O和little-o之间的差别，Big-O为 $0 <= f(n) <= cg(n)$ ，而little-o为 $0<=f(n)<cg(n)$ ，两者主要差别在 $f(n)=o(g(n))$ ，也就是函数的增长率是小於还是严格小於的差别，因此little-o是比Big-O还要来得强烈的叙述，little-o是比较小的函数集合。

ω(读做little-omega)，概念上是大於的概念，也就是 $f(n)$ 增长率严格大於 $g(n)$

来源

函数集合之间的比较关系

$f(n)=$ Θ $(g(n))\ and\ g(n)=$ Θ $(h(n))$ 蕴含 $f(n)=$ Θ $(h(n))$
$f(n)= O(g(n))\ and\ g(n)=O(h(n))$ 蕴含 $f(n)=O(h(n))$
$f(n)=$ Ω $(g(n))\ and\ g(n)=$ Ω $(h(n))$ 蕴含 $f(n)=$ Ω $(h(n))$
$f(n)= o(g(n))\ and\ g(n)=o(h(n))$ 蕴含 $f(n)=o(h(n))$
$f(n)=$ ω $(g(n))\ and\ g(n)=$ ω $(h(n))$ 蕴含 $f(n)=$ ω $(h(n))$