为什么需要渐进分析

面试与工程里比较算法，很少数「跑了几次循环」的精确次数，而是用 Big O 描述当输入规模 n 变大时，时间或资源如何增长。这样可以在不同机器、不同常数优化下仍做公平对比。

记法含义：T(n) = O(f(n)) 表示存在常数 c、n₀，当 n ≥ n₀ 时总有 T(n) ≤ c·f(n)。常见误解是把 Big O 当成精确运行时间；它只刻画增长阶，O(n) 与 O(2n) 同属一线性阶。

常见时间复杂度阶

| 阶 | 典型场景 | 直觉 | |---|---|---| | O(1) | 哈希命中、数组下标 | 与 n 无关 | | O(log n) | 二分、堆顶、平衡树查找 | 每步减半或按树高 | | O(n) | 单次遍历、双指针一轮 | 线性扫描 | | O(n log n) | 归并/快排、堆排序 | 分治 × 合并 | | O(n²) | 两重循环、朴素 DP 表 | 平方对撞 | | O(2ⁿ) | 子集枚举、朴素回溯 | 指数爆炸 |

均摊复杂度：如动态数组 push 均摊 O(1)，偶尔扩容 O(n) 摊到多次操作上。最坏 vs 平均：快排最坏 O(n²)，随机化或三路划分后期望 O(n log n)；面试要说清你分析的是哪一种。

如何分析一段代码

找 n：数组长度、节点数、状态维度乘积等。

数层数：循环嵌套深度、递归深度、每层规模是否减半。

合并：并列循环取最大，嵌套取乘积，递归用主定理或递推式。

# O(n)：单层循环
def sum_arr(a):
    s = 0
    for x in a:      # n 次
        s += x
    return s
O(n log n)：排序主导
def top_k(a, k):
    a.sort()         # O(n log n)
    return a[-k:]
O(n²)：两重循环
def has_pair_sum_zero(a):
    for i in range(len(a)):
        for j in range(i + 1, len(a)):
            if a[i] + a[j] == 0:
                return True
    return False

递归例：斐波那契朴素递归 T(n)=T(n-1)+T(n-2)+O(1) 近似 O(2ⁿ)；记忆化后每个子问题只求一次，状态数 × 单次代价 → O(n)。

空间复杂度要点

• 原地算法：辅助空间 O(1)，如双指针、原地交换。
• 递归栈：深度 h 时栈空间 O(h)，树最深路径即最坏。
• 辅助结构：哈希表、队列、DP 数组各算 O(规模)。

面试答题模板：先说暴力复杂度与瓶颈，再说优化思路及优化后时间/空间，最后提边界（n=0、已排序、重复元素）。能写清主导项，比背公式更有说服力。