算法复杂度

算法复杂度用大 O 记号描述"数据规模增长时，运行时间或内存开销的增长趋势"，是衡量算法好坏的第一把尺子。面试中一切"为什么这个方案更优"的讨论，最终都落到复杂度上；学会估算复杂度，才能快速判断一个解法是否可行。

什么是大 O 记号

设输入规模为 n，记算法耗时为 T(n)。大 O 表示 T(n) 的渐进上界，只保留增长最快的项并忽略常数：

T(n) = 3n² + 5n + 8   →   O(n²)

大 O 描述的是"规模趋于无穷时的趋势"，因此常数、低阶项都不影响结论：O(2n) 与 O(100n) 都写作 O(n)。对应还有 Ω（下界）与 Θ（紧界），面试通常只谈大 O。

常见复杂度量级

记号	名称	典型场景
O(1)	常数	数组按下标取值、哈希查找
O(log n)	对数	二分查找、平衡树操作
O(n)	线性	遍历数组/链表、字符串扫描
O(n log n)	线性对数	快排、归并、堆排序
O(n²)	平方	双层循环、冒泡/插入排序
O(2ⁿ) / O(n!)	指数/阶乘	暴力枚举子集、全排列

规模 n=10⁶ 时：O(n) 一次循环很快，O(n²) 约 10¹² 次操作会跑数十分钟，O(2ⁿ) 更是不可行——这就是为什么说"数据量大时平方级算法会超时"。

分析循环与递归

def sum_naive(n):          # 单层循环 → O(n)
    s = 0
    for i in range(1, n + 1):
        s += i
    return s

def sum_formula(n):        # 等差数列公式 → O(1)
    return n * (n + 1) // 2

print(sum_naive(100), sum_formula(100))   # 输出：5050 5050

循环层数相乘、顺序代码相加是基本规则：两层嵌套各跑 n 次为 O(n²)。递归复杂度常用主定理或递推树分析，例如 T(n) = 2T(n/2) + O(n) 的解为 O(n log n)（归并排序）。

最好、最坏与平均复杂度

同一算法在不同输入下表现不同：快排最好 O(n log n)、最坏 O(n²)（已有序且枢轴取端点）；用随机化（随机选枢轴）可让最坏情况几乎不出现。平均复杂度更贴近真实表现，但分析麻烦，工程上常以"最坏是否可接受"作为取舍标准。

均摊复杂度

均摊分析针对"偶发昂贵操作"的结构：动态数组（如 Python list、Java ArrayList）扩容时要整体搬迁为 O(n)，但扩容不频繁。把搬迁成本分摊到每次 append 上，平均每次 append 仍为 O(1) 均摊——这正是 list 尾插"整体 O(n) 却实际飞快"的原因。

空间复杂度

空间复杂度同样用大 O 描述：原地排序（快排、堆排）为 O(1) 辅助空间，归并排序为 O(n)。做题时先看数据规模：n ≤ 10⁶ 通常可接受 O(n) 时间与空间，n ≤ 10³ 时 O(n²) 也在安全区，据此可快速判断方案是否达标。

小结

复杂度是算法题的"入场券"：会估算时间与空间、会说清最好/最坏/均摊，才能解释清楚"为什么这个算法更快"。拿到题目先算规模、再定复杂度目标，是标准的第一步。