1.1 复杂度是什么
先约定输入规模与计数单位，再看数据变大时需要多做多少工作。本页用 Python 3 的短程序区分增长阶、实际步骤与运行时间。
先把三个词分开
复杂度入门最容易把下面三件事混在一起：
| 词 | 本章怎样理解 | 例子 |
|---|---|---|
| 输入规模 | 用一个或多个变量描述问题有多大 | 数组有 n 个元素 |
| 基本操作 | 选定一种有代表性的工作来计数 | 比较一次、访问一个元素 |
| 增长阶 | 输入变大时，操作次数怎样增长 | Θ(n)、O(n²) |
分析 for value in values 之前，先说 n = len(values)。分析两个数组时，应分别用 n 和 m；除非题目说明两者一样长，否则不能擅自把它们都叫作 n。
我们通常采用一个简化的“单位成本模型”：数组取值、整数加法、比较等基本操作各算一步。它适合观察增长趋势，却不是现实机器的完整画像。长字符串比较、哈希、大整数运算、内存分配和 I/O 的成本可能并非常数。
你遇到的第一个谜题
输入是含 n 个整数编号的数组。任务是统计有多少个无序位置对满足编号数值不相邻；例如 1 与 2 不合法，1 与 3 合法。先写清输入规模和基本操作，再比较枚举与优化方案。
def count_allowed_pairs(resources):
count = 0
for left in range(len(resources)):
for right in range(left + 1, len(resources)):
if abs(resources[left] - resources[right]) != 1:
count += 1
return count程序检查了 n(n - 1)/2 个位置对，所以时间按 Θ(n²) 增长，辅助空间是 Θ(1)。相同编号也可以配对，因为它们的差是 0；重复元素按位置分别计数。这里只返回数量，因此可以先算全部位置对，再减去数值相邻的组合：
from collections import Counter
def count_allowed_pairs_fast(resources):
frequencies = Counter(resources)
total = len(resources) * (len(resources) - 1) // 2
adjacent = sum(count * frequencies.get(value + 1, 0)
for value, count in frequencies.items())
return total - adjacent
assert count_allowed_pairs_fast([-1, 0, 0, 2]) == 4
assert count_allowed_pairs_fast([]) == 0每组相邻值只沿 value → value + 1 计算一次。令 u 为不同编号的数量，在常数成本整数运算和通常的哈希假设下，期望时间为 Θ(n)，辅助空间为 Θ(u)。若要实际列出全部配对，输出成本仍须另算。
大 O 到底说了什么
大 O 描述的是一个渐近上界。直觉上，若输入足够大以后，算法的工作量始终不会超过某个常数倍的 g(n)，就可以写成 O(g(n))。
例如，某段代码执行 3n + 7 次模型操作：
- 它是
O(n)，因为输入足够大后，3n + 7能被某个常数倍的n盖住； - 它也是较松的
O(n²)； - 若要表达“增长速度确实与
n同阶”，更准确的写法是Θ(n)。
日常讨论常把“Big O”当作复杂度统称，但不要把它背成“最坏情况”。最坏情况是在选择哪一组输入；大 O 是给选定的成本函数加上界。完成常见代码推导后，第三篇会把 O、Ω、Θ 和最好、最坏、平均情况正式拆开。
为什么可以丢掉常数和低阶项
假设两个方案的模型工作量分别是：
A(n) = 3n + 7
B(n) = n² + 2n + 1当 n 越来越大时，3n + 7 的主导部分是 n，所以写作 Θ(n)；n² + 2n + 1 的主导部分是 n²，所以写作 Θ(n²)。
这一步只是在归类增长趋势。它不代表常数永远没用，也不代表两个同为 Θ(n) 的程序实际耗时相同。数据规模较小、常数差异很大或缓存行为不同时，工程结果仍要靠测量确认。
七类常见增长速度
下表里的代表式是为了比较增长，不是承诺程序一定执行这么多条指令。
| 增长类 | 常见名称 | 代表式 | 常见场景 |
|---|---|---|---|
Θ(1) | 常数 | 1 | 按下标读取数组元素 |
Θ(log n) | 对数 | ⌊log₂ n⌋ | 每轮把搜索区间减半 |
Θ(n) | 线性 | n | 扫描全部元素 |
Θ(n log n) | 线性对数 | n log₂ n | 归并排序 |
Θ(n²) | 平方 | n² | 检查所有有序元素对 |
Θ(2ⁿ) | 指数 | 2ⁿ | 访问所有子集，不复制成员 |
Θ(n!) | 阶乘 | n! | 访问所有排列，不复制成员 |
如果把每个子集复制为列表，全部输出共包含 n·2^(n-1) 个元素；把每个排列复制为列表则有 n·n! 个元素。此时输出时间和空间分别达到 Θ(n·2ⁿ) 与 Θ(n·n!)，不能只数叶子数量。
几个有用的读法：
- 常数时间不是“只执行一条语句”，而是操作数不随
n增长。 - 对数时间来自反复按固定比例缩小问题。固定底数只带来常数倍差异，所以渐近记号里通常省略底数。
n log n比n多一个会缓慢增长的因子，不能笼统说成“几乎一样快”。- 指数和阶乘增长很快，但小输入仍可能可用。是否可用要结合真实约束，而不是看见符号就下结论。
把增长变成可检查的步骤
下面的程序不计时。它在 n = 8 时，明确执行并统计五种循环模型。这样可以验证“为什么是这个增长阶”，又不会把某台机器的偶然速度写成规律。
# growth_demo.py
def require_positive(n: int) -> None:
if n <= 0:
raise ValueError("n must be positive")
def constant_steps(n: int) -> int:
require_positive(n)
return 1
def logarithmic_steps(n: int) -> int:
require_positive(n)
steps = 0
remaining = n
while remaining > 1:
remaining //= 2
steps += 1
return steps
def linear_steps(n: int) -> int:
require_positive(n)
steps = 0
for _ in range(n):
steps += 1
return steps
def linearithmic_steps(n: int) -> int:
require_positive(n)
steps = 0
for _ in range(n):
remaining = n
while remaining > 1:
remaining //= 2
steps += 1
return steps
def quadratic_steps(n: int) -> int:
require_positive(n)
steps = 0
for _ in range(n):
for _ in range(n):
steps += 1
return steps
def main() -> None:
n = 8
counts = {
"constant": constant_steps(n),
"logarithmic": logarithmic_steps(n),
"linear": linear_steps(n),
"linearithmic": linearithmic_steps(n),
"quadratic": quadratic_steps(n),
}
assert counts == {
"constant": 1,
"logarithmic": 3,
"linear": 8,
"linearithmic": 24,
"quadratic": 64,
}
print(f"n：{n}")
print(f"O(1) 模型步骤：{counts['constant']}")
print(f"O(log n) 模型步骤：{counts['logarithmic']}")
print(f"O(n) 模型步骤：{counts['linear']}")
print(f"O(n log n) 模型步骤：{counts['linearithmic']}")
print(f"O(n²) 模型步骤：{counts['quadratic']}")
print("增长检查通过")
if __name__ == "__main__":
main()运行：
python3 growth_demo.py输出：
n：8
O(1) 模型步骤：1
O(log n) 模型步骤：3
O(n) 模型步骤：8
O(n log n) 模型步骤：24
O(n²) 模型步骤：64
增长检查通过观察对数模型：8 → 4 → 2 → 1，共缩小三次。若 n 不是 2 的整数次幂，具体轮数与循环边界有关；复杂度仍是 Θ(log n)。
从代码认出增长模式
常数：工作量不依赖输入长度
def first(values):
if not values:
return None
return values[0]这里把数组下标访问视为常数成本，因此时间是 Θ(1)。函数是否先检查空数组不改变增长阶。
线性：每个元素处理一次
def contains(values, target):
for value in values:
if value == target:
return True
return False若目标在第一个位置，最好情况是 Θ(1)；若目标不存在，需要检查 n 个元素，最坏情况是 Θ(n)。这也说明“大 O”和“最坏情况”是两个不同维度。
平方：完整的双重范围
def all_ordered_pairs(values):
pairs = []
for left in values:
for right in values:
pairs.append((left, right))
return pairs外层 n 次，每次内层又执行 n 次，共产生 n² 对，所以时间和输出空间都是 Θ(n²)。空间分析必须说明这里计入了返回结果。
三个常见误会
“O(n) 就是正好执行 n 步”
不是。O(n) 是上界类别。5n + 100、n/2 和 n 都可以是线性增长；若上下界都为线性，可以写成 Θ(n)。
“数据翻倍，程序一定按表格倍数变慢”
复杂度说的是模型工作量的长期趋势。实际时间还受缓存、编译器、解释器、内存分配和输入内容影响。应把复杂度分析和基准测试配合使用。
“只要看见两层循环就是 O(n²)”
还要看每层循环的范围。若外层遍历 n 个元素，内层遍历另一个长度为 m 的数组，时间是 Θ(nm)；若两层循环先后执行，则要相加。下一页会用可运行代码逐项推导。
你的第一次分析
为下面三个函数分别写出：输入规模、基本操作、最好情况和最坏情况。
def last(values):
return values[-1]
def count_positive(values):
count = 0
for value in values:
if value > 0:
count += 1
return count
def find_duplicate(values):
for left in range(len(values)):
for right in range(left + 1, len(values)):
if values[left] == values[right]:
return True
return False参考结论：
last在数组支持常数时间下标访问的前提下是Θ(1)；空列表会抛IndexError，因此“返回最后一项”的契约还要求输入非空。count_positive无论正数多少都扫描全部元素，时间是Θ(n)，辅助空间是Θ(1)。find_duplicate找到开头的一对重复值时可以很快返回；没有重复值时检查n(n - 1)/2对，最坏时间是Θ(n²)，辅助空间是Θ(1)。
用三行记录第一次分析
面对一段代码，先写 n 代表什么，再选一种模型操作，最后写出操作次数如何随 n 增长。对 last、count_positive 和 find_duplicate 分别完成这三行，并单独报告最好与最坏情况。
把 n = 8 改成 16，核对线性、线性对数和平方模型分别变成 16、64 和 256。这个实验验证的是模型步骤，不是墙上时钟；实际运行时间还要受解释器、缓存和输入内容影响。
每次分析前先写下 n 的含义和所数的操作；同一程序换一种成本口径，结论也要跟着调整。
下一步：把代码形状算成表达式
下一篇会处理顺序代码、依赖范围的嵌套循环、二分过程、多个输入、输出空间和隐藏的库操作成本。