【算法设计与分析】04 函数的渐进的界

今天学习函数的渐进的界，会涉及多种数学符号。对以后学习分析算法复杂度有很大的帮助。

1 大 $O$O符号

• 定义： 设 f 和 g是定义域为自然数集N上的函数. 若存在正数 c 和 n₀， 使得
  对一切 n $\ge$≥ n₀有:
  $c\le f\left(n\right)\le cg\left(n\right)$c≤f(n)≤cg(n)
  成立。则称f(n)的渐近的上届是g(n)。记作：
  $f\left(n\right)=O\left(g\right(n\left)\right)$f(n)=O(g(n))

例子：

• 设 $f\left(n\right)=n^2+2$f(n)=n2+2,则
  $f\left(n\right)=O\left(n^2\right),取c=2，n_0=1即可$f(n)=O(n2),取c=2，n0​=1即可
  $f\left(n\right)=O\left(n^3\right),取c=3，n_0=2即可$f(n)=O(n3),取c=3，n0​=2即可

对于大 $O$O符号，有一下几条概念需要注意：

1. $f\left(n\right)=O\left(g\right(n\left)\right),f\left(n\right)的阶不高于g\left(n\right)的阶$f(n)=O(g(n)),f(n)的阶不高于g(n)的阶
2. 可能存在多个正数c，只要指出其中一个即可，
3. 对前面有限个值可以不满足不等式
4. 常函数可以写成 $O\left(1\right)$O(1)。

2 大 $\Omega$Ω符号

• 定义：设 f 和 g是定义域为自然数集N上的函数. 若存在正数 c 和 n₀，使得对一切 n $\ge$≥ n0有：

$0\le cg\left(n\right)\le f\left(n\right)$0≤cg(n)≤f(n)
成立。则称 $f\left(n\right)$f(n)的渐近的下届是 $g\left(n\right)$g(n)，记作：
$f\left(n\right)=\Omega \left(g\right(n\left)\right)$f(n)=Ω(g(n))

例子：

• 设 $f\left(n\right)=n^2+2$f(n)=n2+2,则
  $f\left(n\right)=\Omega \left(n^2\right),取c=1，n_0=1即可$f(n)=Ω(n2),取c=1，n0​=1即可
  $f\left(n\right)=\Omega \left(100n\right),取c=1/100，n_0=1即可$f(n)=Ω(100n),取c=1/100，n0​=1即可

对于 $\Omega$Ω符号，需要注意以下几点：

1. $f\left(n\right)=\Omega \left(g\right(n\left)\right),f\left(n\right)的阶不低于g\left(n\right)的阶$f(n)=Ω(g(n)),f(n)的阶不低于g(n)的阶
2. 可能存在多个正数c，只要指出其中一个即可
3. 对前面有限个n值可以不满足上述不等式

3 小 $o$o符号

• 定义：设 f 和 g是定义域为自然数集N上的函数. 若对任意正数 c 都存在 n₀，使得对一切 n $\ge$≥ n₀有：
  0≤f(n)<cg(n)
  成立。则记作：
  $f\left(n\right)=o\left(g\right(n\left)\right)$f(n)=o(g(n))

例子：

• 设 $f\left(n\right)=n^2+2$f(n)=n2+2,则
  f(n)=o(n3),c≥1显然成立。因为n2+n<cn3（n0​=2）
  $对于1>c>0，取n_0>\lceil \frac{2}{c}\rceil 即可，因为：$对于1>c>0，取n0​>⌈c2​⌉即可，因为：
  $cn\ge c{n}_0>2$cn≥cn0​>2 （当n $\ge n_0$≥n0​）
  n2+n<2n2<cn3

对于小 $o$o符号，需要注意以下几点：

1. $f\left(n\right)=o\left(g\right(n\left)\right),f\left(n\right)的阶低于g\left(n\right)的阶$f(n)=o(g(n)),f(n)的阶低于g(n)的阶
2. 对不同正数c，n₀ 不一样，c越小，n₀越大。
3. 对前面有限个n值可以不满足上述不等式

4 小 $\omega$ω符号

• 定义：设 f 和 g是定义域为自然数集N上的函数. 若对任意正数 c 都存在 n₀，使得对一切 n $\ge$≥ n₀有：
  0≤cg(n)<f(n)
  成立。则记作：
  $f\left(n\right)=\omega \left(g\right(n\left)\right)$f(n)=ω(g(n))

例子：

• 设 $f\left(n\right)=n^2+2$f(n)=n2+2,则
  $f\left(n\right)=\omega \left(n\right),不能写f\left(n\right)=\omega \left(n^2\right),因为取c=2，不存在n_0，使得对一切n\ge n_0有下式成立$f(n)=ω(n),不能写f(n)=ω(n2),因为取c=2，不存在n0​，使得对一切n≥n0​有下式成立
  cn2=2n2<n2+n（不成立）

对于小 $\omega$ω符号，需要注意以下几点：

1. $f\left(n\right)=\omega \left(g\right(n\left)\right),f\left(n\right)的阶高于g\left(n\right)的阶.$f(n)=ω(g(n)),f(n)的阶高于g(n)的阶.
2. $对不同的正数c,n_0不等，c越大n_0越大.$对不同的正数c,n0​不等，c越大n0​越大.
3. 对前面有限个 n 值可以 不满足不等式.

5 $\Theta$Θ符号

• 定义：若 $f\left(n\right)=O\left(g\right(n\left)\right)且f\left(n\right)=\Omega \left(g\right(n\left)\right),$f(n)=O(g(n))且f(n)=Ω(g(n)),则记作：

$f\left(n\right)=\Theta \left(g\right(n\left)\right)$f(n)=Θ(g(n))

例子： $f\left(n\right)=n^2+n,g\left(n\right)=100n^2，那么有$f(n)=n2+n,g(n)=100n2，那么有
$f\left(n\right)=\Theta \left(g\right(n\left)\right)$f(n)=Θ(g(n))

注意以下两点：

1. $f\left(n\right)的阶与g\left(n\right)的阶相等$f(n)的阶与g(n)的阶相等
2. 对前面有限个n值，可以不满足条件

6 总结

• 五种表示函数的阶的符号： $O,\Omega ,o,\omega ,\Theta$O,Ω,o,ω,Θ
• 理解它们的定义
• 如何用定义证明函数的阶？下一篇文章继续学习。