复杂度分析：推演算法的“上限”

在算法世界里，代码运行快慢不仅仅取决于你的 CPU 频率，更取决于你写的代码随数据增长的趋势。复杂度分析就是这套终极评估工具。

为什么不能只靠实测（跑分）？

很多新手喜欢用 startTime - endTime 来测速。但这有三大坑：

1. 环境偏差：你的 i9 电脑跑 1 秒，别人的树莓派可能跑 1 小时。
2. 数据热点：小规模数据（如 10 个数）看不出 $O(n)$ 和 $O(n^2)$ 的区别。
3. 预测性差：你无法在写代码前知道它在 1 亿条数据下表现如何。

复杂度分析的本质：脱离硬件，只谈代码执行步数随 $n$ 增长的数学趋势。

---

时间复杂度：大 O 表示法

大 O 表示法 ($O(f(n))$) 描述的是算法执行时间的渐进上界。简言之，就是“最坏情况下，它增长得多快”。

常见的复杂度“段位”

符号	名称	程序员的直观感受
$O(1)$	常数阶	极速。哈希查找、数组下标访问。
$O(\log n)$	对数阶	飞快。二分查找、平衡树。
$O(n)$	线性阶	正常。遍历一遍列表。
$O(n \log n)$	线性对数阶	卓越。快速排序、归并排序的标配。
$O(n^2)$	平方阶	危险。双重循环。$n=1万$ 时就开始卡顿。
$O(2^n)$	指数阶	噩梦。未优化的递归、穷举子集。

---

避坑：大 O 计算的三大铁律

1. 抓大放小 (只看最高阶)

如果你的步数是 $2n^2 + 10n + 1000$，在 $n$ 趋近无穷大时，后两项的影响微乎其微。

• 结论：直接简写为 $O(n^2)$。

2. 去掉常数项

$O(2n)$ 和 $O(100n)$ 在趋势上看都是线性的。

• 结论：都写成 $O(n)$。

3. 多层嵌套相乘

如果你外面一个 $O(n)$ 循环，里面套一个 $O(\log n)$ 的二分查找。

• 结论：总复杂度是 $O(n \cdot \log n)$。

---

案例深究：从递归到主定理

很多同学卡在递归题的复杂度分析上。比如归并排序： $T(n) = 2T(n/2) + O(n)$

我们可以用主定理 (Master Theorem) 快速口算： 对于 $T(n) = aT(n/b) + f(n)$ 型递归：

• 如果 $f(n)$ 是线性增长（如合并操作），且 $a=b=2$。
• 那么结果就是 $O(n \log n)$。

---

空间复杂度：内存的“房租”

空间复杂度衡量的是算法执行过程中额外开辟的内存。

• $O(1)$：只用了几个变量。
• $O(n)$：开了一个跟输入一样大的数组。
• $O(\log n)$：通常见于二分查找的递归版本，虽然没开数组，但递归调用栈占用了 $\log n$ 层。

[!TIP] 空间换时间是算法优化的核心思想。比如用 哈希表 ($O(n)$ 空间) 把二层循环的 $O(n^2)$ 查找降到 $O(1)$。

---

复杂度分析的“三境”

1. 最好情况 (Best Case)：你运气极好，第一个数就是你要找的。$O(1)$。
2. 最坏情况 (Worst Case)：你得查到最后一个才发现。$O(n)$。这是我们最关注的，代表了系统的兜底性能。
3. 平均情况 (Average Case)：所有输入概率均等下的数学期望。

---

练习题：考考你的眼力

请口算以下 Python 片段的复杂度：

# 片段 A
def demoA(n):
    for i in range(n):
        for j in range(100): # 注意这个 100
             print(i, j)

# 片段 B
def demoB(n):
    i = 1
    while i < n:
        i *= 2 # 注意这个乘 2
        print(i)

答案解析：

• 片段 A：$O(n)$。因为内层循环是常数项 100，不随 $n$ 变化。
• 片段 B：$O(\log n)$。因为 $i$ 是指数增长，达到 $n$ 只需要 $\log_2 n$ 步。

---

总结

复杂度分析不是数学考试，它是程序员的工程直觉。

• 如果你在处理数百万条数据，看到 $O(n^2)$ 的算法，你应该立即警觉。
• 如果你在嵌入式设备（如 Arduino）上，看到 $O(n)$ 的空间占用，你应该考虑是否会内存溢出。

[!IMPORTANT] 掌握了复杂度，你就拥有了评判一段代码“好坏”的唯一客观标准。接下来，去看看我们的算法速查表中各种常用操作的复杂度。