渐近分析

阐述

用于理解算法在输入长度越来越大时的行为。

渐近上界（大 O 标记）

设 $f,g:\mathbb N\to\mathbb R^+$，称 $f(n)=O(g(n))$，如果存在正整数 $c,n_0$ 使得对于每个整数 $n\ge n_0$ 都有 $f(n)\le cg(n)$。$g(n)$ 为 $f(n)$ 的渐近上界。

若 $g(n)=n^c(c>0)$，则称它为多项式上界；若 $g(n)=2^{(n^\delta)}(\delta>0)$，则称它为指数上界。

渐近小于（小 o 标记）

设 $f,g:\mathbb N\to\mathbb R^+$，称 $f(n)=o(g(n))$，如果对任意正实数 $c$ 都存在正整数 $n_0$ 使得对于每个整数 $n\ge n_0$ 都有 $f(n)<cg(n)$。也即

$$\lim _{n \rightarrow \infty} \frac{f(n)}{g(n)}=0$$

实例

性质

相关内容

参考文献