算法设计与分析：时间复杂度

发表于 2021-12-26 分类于算法本文字数： 818

参考资料：北大公开课算法设计与分析屈婉玲教授

函数渐近的界

设 $f$ 和 $g$ 是定义域为自然数集 $N$ 上的函数，若存在正数 $c$ 和 $n_{0}$ ，使得对一切的 $n \leq n_{0}$ 有

0 \leq f (n) \leq c g (n)

成立，则称 $f (n)$ 渐近的上界为 $g (n)$ ，记作：

f (n) = O (g (n))

注意：

$f (n) = O (g (n))$ 中， $f (n)$ 的阶小于等于 $g (n)$ 的阶

设 $f$ 和 $g$ 是定义域为自然数集 $N$ 上的函数，若存在正数 $c$ 和 $n_{0}$ ，使得对一切的 $n \leq n_{0}$ （前面与 $O (n)$ 相同）有：

0 \leq c g (n) \leq f (n)

成立，则称 $f (n)$ 的 渐近的下界 为 $g (n)$ ，记作

f (n) = Ω (g (n))

设 $f$ 和 $g$ 是定义域为自然数集 $N$ 上的函数，对任意的正数 $c$ ，都存在 $n_{0}$ ，使得 $n \geq n_{0}$ 有

0 \leq f (n) < c g (n)

若成立，则记作

f (n) = o (g (n))

和 $o (n)$ 类似，表示的是下界且 $g (n)$ 增长得比 $f (n)$ 慢。

0 \leq c g (n) < f (n)

f (n) = Ω (g (n)) f (n) = O (g (n))

若上面两条等式成立，即 $g (n)$ 同时为 $f (n)$ 的渐近上界和渐近下界，则称

f (n) = Θ (g (n))

表示的是：

设 $c$ 为某个常数且 $c > 0$

lim_{n \to \infty} \frac{f (n)}{g (n)} = c ⟺ f (n) = Θ (g (n)) lim_{n \to \infty} \frac{f (n)}{g (n)} = 0 ⟺ f (n) = o (g (n)) lim_{n \to \infty} \frac{f (n)}{g (n)} = + \infty ⟺ f (n) = ω (g (n))

指数函数的阶大于多项式函数的阶

n^{d} = o (r^{n}) r > 1, d > 0

\ln n = o (n^{d}) d > 0

对数函数的阶低于幂函数的阶

$O, Ω, Θ$ 关系具有传递性

f = O (h) g = O (h) \to f + g = O (h)

n! = o (n^{n}) n! = ω (2^{n}) \log (n!) = Θ (n \log n)

等差、等比与调和级数

\sum_{k + 1}^{n} a_{k} = \frac{n (a_{1} + a_{n})}{2} \sum_{k = 0}^{n} a q^{k} = \frac{a (1 - q^{n + 1})}{1 - q}, \sum_{k = 0}^{\infty} a q^{k} = \frac{a}{1 - q} (q < 1) \sum_{k = 1}^{n} \frac{1}{k} = \ln n + O (1)