元数据卡
- 前置知识：编程基础（Vol 1）
- 预计时间：10 分钟
- 完成标志：能理解大 O 记号的含义，能区分常见复杂度
你的进度
你告别了变量村，背着行囊走进了村后的算法森林。老陈师傅递给你一张泛黄的地图——上面画着一条蜿蜒的路和一行字：
"这是复杂度分析。它会告诉你哪条路走得通、哪条路会困死你。"
后山小道走到尽头，你眼前是一座陡峭的瞭望台。上山的路还有好几条——有人背着满背包的试炼题册，有人满头大汗地翻着前人笔记问什么叫 O(n²)。
这个瞭望台叫"复杂度分析"。它不教你写代码。它教你——在还不写代码的时候，就知道一段代码的命有多长。
你遇到了第一个谜题
林间驿站有 N 份干粮需要配对发放，每个冒险者领一份主粮和一份配粮，但编号相邻的两份（比如 1 号和 2 号）不能发放。最多能发出几份？
最直觉的解法是这样：
python
def max_meals(orders):
n = len(orders)
count = 0
for i in range(n):
for j in range(i + 1, n):
if abs(orders[i] - orders[j]) != 1:
count += 1
return count这个跑法叫"两两检查"——干粮只有 10 份的时候还行，有 1000 份的时候你就要等很久了。
为什么？因为内部的循环规模是 n²（外层 n 次，内层每次也接近 n 次）。n 从 1000 到 2000 只翻了一倍，工作量却从 1000000 暴涨到 4000000——翻了四倍。
大 O 是什么
大 O 记号不关心精确的运行时间——它只关心增长趋势。
python
# O(1)——常数时间：不管数据多大，一步做完
def first_element(arr):
return arr[0]
# O(n)——线性时间：数据翻倍，时间翻倍
def find_max(arr):
max_val = arr[0]
for x in arr:
if x > max_val:
max_val = x
return max_val
# O(n²)——平方时间：数据翻倍，时间翻四倍
def has_duplicates(arr):
for i in range(len(arr)):
for j in range(i + 1, len(arr)):
if arr[i] == arr[j]:
return True
return False简化规则：
- 只保留最高阶项：
n² + n→n² - 丢弃常数因子：
2n + 100→n - 忽略低阶项：
n² + 100n + 1000→n²
常见复杂度图谱
| 复杂度 | 名称 | n=10 | n=100 | n=1000 |
|---|---|---|---|---|
| O(1) | 常数 | 1 | 1 | 1 |
| O(log n) | 对数 | 3 | 7 | 10 |
| O(n) | 线性 | 10 | 100 | 1000 |
| O(n log n) | 线性对数 | 33 | 700 | 10000 |
| O(n²) | 平方 | 100 | 10000 | 1000000 |
| O(2ⁿ) | 指数 | 1024 | 天文数字 | 不可能 |
O(n log n) 就是 O(n) 再乘一个 log n。log n 增长极慢——n 从 1 到 10 亿，log₂ n 才到 30。所以 O(n log n) 几乎和 O(n) 差不多快。
旅人笔记
大 O 标记的是增长的"趋势"，不是精确的速度。O(n²) 和 O(n) 之间的差距不是常数倍，是质变——数据规模每翻一倍，前者工作量翻四倍，后者只翻一倍。
→ 下一步：常见复杂度分析
复杂度不只是概念——你要学会给真实的代码"算复杂度"。