渐近记号与函数增长

渐近分析关心 $n$ 足够大时的增长速度，忽略常数倍和低阶项。它不是“把公式写得模糊一点”，而是用严格量词描述函数之间的长期关系。

1. 五个渐近记号

设 $f(n),g(n)$ 在充分大的 $n$ 上非负。

1.1 渐近上界 $O$

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

表示存在常数 $c>0,n_0$ ，使所有 $n\ge n_0$ 都有

0\le f(n)\le cg(n).

它只表示“不比 $g$ 增长得更快”。例如 $3n+7=O(n^2)$ 也正确，只是不紧。

1.2 渐近下界 $\Omega$

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

表示存在 $c>0,n_0$ ，使 $n\ge n_0$ 时

0\le cg(n)\le f(n).

1.3 紧确界 $\Theta$

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

表示同时有 $f(n)=O(g(n))$ 和 $f(n)=\Omega(g(n))$ 。也就是 $g$ 在常数倍意义下准确描述了 $f$ 的增长阶。

1.4 严格上界 $o$ 与严格下界 $\omega$

f(n)=o(g(n)) \iff \lim_{n\to\infty}\frac{f(n)}{g(n)}=0,

f(n)=\omega(g(n)) \iff \lim_{n\to\infty}\frac{f(n)}{g(n)}=\infty.

$n=o(n^2)$ ，但 $n\ne o(n)$ 。小写记号排除了“同阶”的情况。

2. 用极限快速比较

考察

L=\lim_{n\to\infty}\frac{f(n)}{g(n)}.

$0<L<\infty$ ： $f=\Theta(g)$ ；
$L=0$ ： $f=o(g)$ ；
$L=\infty$ ： $f=\omega(g)$ 。

极限不存在时，不能直接下结论。例如 $f(n)=n(2+\sin n)$ 与 $n$ 的比值不收敛，但始终夹在 $n$ 和 $3n$ 之间，所以仍有 $f(n)=\Theta(n)$ 。

3. 常见增长顺序

对固定常数 $k>0$ 、 $a>1$ ：

1 \prec \log\log n \prec \log n \prec (\log n)^k \prec n^\varepsilon \prec n \prec n^k \prec a^n \prec n! \prec n^n.

这里 $\varepsilon>0$ 可以很小。一个重要结论是：任意正次数多项式最终都比任意对数幂增长快，而任意固定底数指数最终都比任意多项式增长快。

对数底数只差常数：

\log_a n=\frac{\log_b n}{\log_b a}=\Theta(\log n).

4. 多项式、和与乘积

对多项式

p(n)=a_dn^d+\cdots+a_1n+a_0,

若 $a_d>0$ ，则 $p(n)=\Theta(n^d)$ 。

常用规则：

O(f)+O(g)=O(\max\{f,g\}),

O(f)\cdot O(g)=O(fg).

顺序执行的两段程序取较大复杂度；嵌套执行通常相乘。但“循环嵌套”不一定机械相乘，内层迭代次数可能依赖外层变量，必须求和。

5. 常见求和

5.1 等差与幂和

\sum_{i=1}^n i=\Theta(n^2), \qquad \sum_{i=1}^n i^k=\Theta(n^{k+1}).

5.2 调和级数

\sum_{i=1}^n\frac1i=\Theta(\log n).

因此下面循环不是 $O(n^2)$ ：

for i = 1 .. n:
    for j = 1; j <= n; j += i:
        constant_work()

第 $i$ 轮约执行 $n/i$ 次，总计

n\sum_{i=1}^n\frac1i=\Theta(n\log n).

5.3 几何级数

当 $0<r<1$ 时，

1+r+r^2+\cdots=\Theta(1).

当 $r>1$ 时，有限几何级数由最后一项主导。这是分析递归树的核心工具。

6. 传递性与对称性

$O$ 、 $\Omega$ 、 $\Theta$ 都具有传递性；
$f=\Theta(g)$ 具有对称性；
$f=O(g)$ 等价于 $g=\Omega(f)$ ；
若 $f=O(g)$ ，不能推出 $f=\Theta(g)$ 。

写“算法复杂度是 $O(n^2)$ ”通常是在报上界。如果已经证明上下界一致，写 $\Theta(n^2)$ 更准确。

7. 空间复杂度也用同一套记号

原地算法通常指额外空间 $O(1)$ ，但要留意：

递归调用栈；
返回数组或复制切片；
哈希表和队列的最坏规模；
输入是否允许被修改。

例如递归二分查找时间 $O(\log n)$ ，递归栈空间也是 $O(\log n)$ ；改成迭代后可降为 $O(1)$ 。

8. 易错点

$O$ 不是“等于最坏情况”，它只是函数上界；最好、平均、最坏三种情况都能使用 $O$ 。
常数在渐近分析中可忽略，但在实际工程里仍可能决定哪个算法更快。
$O(2n)$ 与 $O(n)$ 相同， $O(2^n)$ 与 $O(n)$ 完全不同。
不能把 $O(f)+O(g)$ 写成 $O(f+g)$ 后就停止；应继续化简到主导项。
对多参数问题不要强行只写一个 $n$ ，例如图算法应保留 $V,E$ 。