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

发表于 2021-12-26 更新于 2024-10-21 分类于算法

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

函数渐近的界

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

0 \leq f(n) \leq cg(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 cg(n) \leq f(n)

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

f(n) = \Omega(g(n))

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

0 \leq f(n) < cg(n)

若成立，则记作

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

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

0 \leq cg(n) < f(n)

f(n) = \Omega(g(n)) \\ f(n) = O(g(n))

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

f(n) = \Theta(g(n))

表示的是：

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

\lim_{n\rightarrow \infty}\frac{f(n)}{g(n)} = c \iff f(n) = \Theta(g(n)) \\ \lim_{n\rightarrow \infty}\frac{f(n)}{g(n)} = 0 \iff f(n) = o(g(n)) \\ \lim_{n\rightarrow \infty}\frac{f(n)}{g(n)} = +\infty \iff f(n) = \omega(g(n))

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

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

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

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

$O, \Omega, \Theta$ 关系具有传递性

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

n! = o(n^n) \\ n! = \omega(2^n) \\ \log(n!) = \Theta(n\log n)

等差、等比与调和级数

\sum^n_{k+1}a_k = \frac{n(a_1 + a_n)}{2} \\ \sum^n_{k=0}aq^k = \frac{a(1-q^{n+1})}{1-q},\sum^\infty_{k=0}aq^k = \frac{a}{1-q}(q<1) \\ \sum^n_{k=1}\frac{1}{k} = \ln n + O(1)