第一章：复杂度与算法分析

本章目标

本章要建立算法分析的第一套语言：用输入规模 n 描述程序成本，而不是只看某一次运行快不快。

学完后，你应该能区分 O(1)、O(log n)、O(n)、O(n^2) 的增长差异，并能解释为什么空间复杂度也会影响真实项目里的选择。

核心概念

时间复杂度关注操作次数随输入增长的趋势。常数项和低阶项通常会被忽略，因为当 n 足够大时，主导项决定算法是否可扩展。

空间复杂度描述额外内存的增长。用哈希表换取查找速度、用数组缓存中间结果，都是典型的时间/空间 tradeoff。

Python 示例

下面的 sum_numbers 会遍历每个元素一次，所以时间复杂度是 O(n)，只使用一个累加变量，额外空间是 O(1)。

def sum_numbers(numbers):
    total = 0
    for number in numbers:
        total += number
    return total

如果列表已经有序，二分查找每次排除一半候选，时间复杂度为 O(log n)，这是用前置有序条件换取查询速度的代表。

复杂度与常见误区

常见误区是只看循环层数。双指针虽然写在一个 while 中，但每个指针总共只移动 n 次，通常仍然是 O(n)。

另一个误区是忽略切片、排序、拷贝等隐藏成本。Python 中 nums[:] 会产生 O(n) 的空间复杂度，sorted(nums) 至少需要 O(n log n) 时间。

本章要点

分析算法时先确定输入规模，再数核心操作的增长趋势，最后检查是否创建了随 n 增长的额外结构。

真实编码中要结合数据规模、常数成本和可读性判断。复杂度是筛选方案的工具，不是替代工程判断的公式。