算法导论复习（二）| 函数增长

渐进记号用于刻画算法的时间复杂度限界函数，主要包括Θ、O、Ω、o、w。

记算法的实际执行时间为f(n)，执行时间的限界函数为g(n)。

上界函数

1.O记号（渐近上界）

定义：如果存在两个正常数c和n0，对于所有的n≥n0，有|f(n)| ≤ c|g(n)|，则记作 f(n)=Ο(g(n))。

O记号给出一个渐进上界。函数f至多是函数g的c倍，除非n<n0。即当n充分大时，g是f的一个上界函数。
应试图找阶最小的g(n)作为f(n)的上界函数， 即g(n)应该尽量接近函数f(n)——紧确。

可用O记号来表示算法的最坏情况时间复杂度。

简单地说，O不一定是紧确的上界（可以包含o），但最好做到紧确。

2.o记号（松散上界）

定义：对任意正常数c，存在常数n0＞0，使对所有的n≥n0，有|f(n)| ≤ c|g(n)|，则记作：f(n) = o(g(n))。

含义：在o表示中，当n趋于无穷时，f(n)相对于g(n)来说变得微不足道了，即
$$\underset{n\to \infty }{\lim }\frac{f(n)}{g(n)}=0$$
例：2n = o(n²)，但2n²≠ o(n²)

---

下界函数

Ω记号（渐近下界）

定义：如果存在两个正常数c和n0，对于所有的n≥n0，有|f(n)| ≥ c|g(n)|，则记作f(n)=Ω(g(n))。

Ω记号给出一个渐进下界。函数f 至少是函数g 的c 倍，除非n<n0。即当n充分大时，g 是f 的一个下界函数。
应试图找出数量级最大的g(n)作为f(n)的下界函数，即g(n)应该尽量接近函数f(n)。

w记号（松散下界）

定义：对任意正常数c，存在常数n0>0，使对所有的n≥n0，有c|g(n)|≤|f(n)| ，则记作：f(n) = ω(g(n))。

含义：在ω表示中，当n趋于无穷时，f(n)相对于g(n)来说变得任意大了，即
$$\underset{n\to \infty }{\lim }\frac{f(n)}{g(n)}=\infty$$
例：n²/2 = ω(n)，但n²/2≠ ω(n²)

---

渐近紧确界函数

1.定义

如果存在正常数c1，c2和n0，对于所有的n≥n0，有c1|g(n)| ≤|f(n)| ≤ c2|g(n)|，则记作f(n)=Θ(g(n))。

文字定义：如果存在正常量c1和c2，使得对于足够大的n，函数f(n)能“夹入” c1g(n) 和 c2g(n)之间，则称f(n)属于集合Θ(g(n)) 。

含义：n对所有的n≥n0，函数f(n)在一个常数因子内等价于g(n)。

称g(n)是f(n)的一个渐进紧确界。

从算法时间复杂度的角度看，就是算法在最好和最坏情况下的计算时间就一个常数因子范围内而言是相同的。可看作既有 f(n) = Ω(g(n))，又有f(n) = Ο(g(n))。 即g 既是f 的下界，又是f 的上界。

2.渐近紧确界的证明

例题：

---

时间复杂度

根据上界函数（渐进紧确上界）的特性，可以将算法分为：多项式时间算法和指数时间算法。

• 多项式时间算法：可用多项式函数对计算时间限界的算法。

  常见的多项式限界函数有：

  Ο(1) < Ο(logn) < Ο(n) < Ο(nlogn) < Ο(n²) < Ο(n³)

• 指数时间算法：计算时间用指数函数限界的算法。

  常见的指数时间限界函数：
  Ο(2ⁿ) < Ο(n!) < Ο(nⁿ)

---