复杂度分析 ​

算法效率的度量语言。刷题和面试中所有「能不能过」「为什么快」的讨论，最终都落到时间复杂度与空间复杂度上。

一、什么是复杂度 ​

1.1 从"运行时间"到"复杂度" ​

• 同一份代码在不同机器、不同输入规模下运行时间不同，无法用秒数直接比较算法。
• 复杂度忽略机器差异与常数系数，只刻画运行时间 / 内存随输入规模 n 增长的趋势。
• 核心问题：当 n 翻倍、n 变成 10 倍时，运行时间大约变成几倍？

1.2 大 O 记号的直觉与含义 ​

• O(f(n)) 表示运行时间的上界量级，即存在常数 c 与 n₀，使 n ≥ n₀ 时 T(n) ≤ c·f(n)。
• 直觉理解：只看「最高阶项」，丢掉常数与低阶项。
  • T(n) = 3n² + 5n + 1 → O(n²)
• 常见发音：O(1) 常数阶、O(log n) 对数阶、O(n) 线性阶、O(n²) 平方阶。

1.3 为什么可以忽略常数与低阶项 ​

• n 足够大时，不同量级之间是「鸿沟」：n² 与 100n 在 n=1e6 时相差 1 万倍。
• 面试里说「O(n) 比 O(n²) 好」指的是渐近意义，不排斥常数优化，但常数优化救不了量级差距。

1.4 常见复杂度量级一览 ​

二、时间复杂度分析 ​

2.1 加法法则（顺序结构） ​

代码段 A 执行 O(f)，随后执行代码段 B 执行 O(g)，整体取较大者：T = O(f + g) = O(max(f, g))。

for x in arr:          # O(n)
    print(x)
for i in range(n):     # O(n^2)
    for j in range(n):
        pass           # 整体 O(n^2)

for x in arr:          # O(n)
    print(x)
for i in range(n):     # O(n^2)
    for j in range(n):
        pass           # 整体 O(n^2)

2.2 乘法法则（嵌套结构） ​

循环体内再套循环，总次数相乘：外层 m 次 × 内层单次 n 步 = O(m·n)。

for i in range(n):          # n 次
    for j in range(m):      # 每次 m 步
        do_something()      # 整体 O(n*m)

for i in range(n):          # n 次
    for j in range(m):      # 每次 m 步
        do_something()      # 整体 O(n*m)

2.3 分析循环的通用写法：数「步数」 ​

• 把问题变成「循环总共执行多少次」的求和式，再化简。
  • for i in range(n) 内 for j in range(i) → 0+1+...+n-1 = n(n-1)/2 → O(n²)
• 步进不是 1 时看步长：i = i * 2 的循环次数是 log₂n。

2.4 对数阶 log n 从哪里来 ​

• 凡是「每轮规模减半 / 除以 k」的，复杂度都含 log n。
• 二分查找、二叉树的高度（平衡时）、倍增法、快速幂都是 O(log n) 或 O(n log n)。

def binary_search(arr, target):          # 每轮区间减半
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1                            # O(log n)

def binary_search(arr, target):          # 每轮区间减半
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1                            # O(log n)

2.5 多个输入规模的情况 ​

• 两个数组长度分别是 n 与 m，且互不相关，复杂度写 O(n+m) 或 O(n·m)，不要合并成 n。
• 面试扣分点：把双串题目强行写 O(n) 而实际是 O(n·m)。

三、空间复杂度分析 ​

3.1 什么是空间复杂度 ​

• 衡量算法额外占用的内存随 n 的增长量级（一般不计输入本身占的空间）。
• 原地算法（in-place）的额外空间是 O(1)。

3.2 常见额外空间开销 ​

3.3 递归的空间 = 递归深度 ​

• 每次递归调用压一层栈，空间是 O(深度) 而非 O(调用总数)。
  • 单链递归求和，n 层 → O(n)；二分递归 log 层 → O(log n)。
• 尾递归与迭代可在部分语言里省栈，Python 不优化尾递归，深递归会 RecursionError。

3.4 时间与空间的取舍 ​

• 经典 trade-off：哈希表空间换时间（两数之和、去重）；滚动数组/状态压缩时间换空间。
• 面试答法：先给朴素解，再说明「用 O(n) 空间换 O(n²)→O(n) 的时间」是否划算。

四、递归复杂度与主定理 ​

4.1 用递归树直观估算 ​

• 把每次调用展开成节点：总工作量 ≈ 每层节点数 × 每节点耗时，再对层求和。

归并排序递归树（n=8）：
        8            ← 第 0 层：1 个节点，合并耗时 O(8)
       / \
      4   4          ← 第 1 层：2 个节点，各 O(4)，合计 O(8)
     / \ / \
    2  2 2  2        ← 第 2 层：合计 O(8)
   / \/\/\/ \
  1 1 1 1 1 1 1 1    ← log n 层
每层合计 O(n)，共 log n 层 → T(n) = O(n log n)

归并排序递归树（n=8）：
        8            ← 第 0 层：1 个节点，合并耗时 O(8)
       / \
      4   4          ← 第 1 层：2 个节点，各 O(4)，合计 O(8)
     / \ / \
    2  2 2  2        ← 第 2 层：合计 O(8)
   / \/\/\/ \
  1 1 1 1 1 1 1 1    ← log n 层
每层合计 O(n)，共 log n 层 → T(n) = O(n log n)

4.2 主定理简介 ​

• 形如 T(n) = a·T(n/b) + O(n^d) 的递推（a 个子问题、规模 n/b、分解合并开销 n^d）：
  • 若 log_b(a) < d：T(n) = O(n^d)（合并开销主导）
  • 若 log_b(a) = d：T(n) = O(n^d · log n)
  • 若 log_b(a) > d：T(n) = O(n^(log_b(a)))（子问题主导）
• 面试只需要会用：归并 T=2T(n/2)+O(n) → 情况二 → O(n log n)。

4.3 典型递归复杂度速查 ​

五、最好、最坏、平均与均摊复杂度 ​

5.1 四种复杂度的含义 ​

5.2 均摊分析：动态数组扩容 ​

• ArrayList/Python list 尾部追加：绝大多数 O(1)，满了要 O(n) 拷贝扩容。
• 总代价均摊到每次 append 上仍是 O(1)（倍增扩容使拷贝次数呈几何级数）。
• 结论话术：「单次可能 O(n)，均摊 O(1)，所以循环 n 次 append 整体 O(n)」。

5.3 什么时候用哪种表述 ​

• 不说明时默认讨论最坏情况；哈希表类结构要说清「理论最坏 O(n)、实际均摊 O(1)」。
• 面试被问「这个算法最好/最坏是多少」：快排最好 O(n log n)，最坏 O(n²)（已有序+固定基准）。

六、常见复杂度曲线对比 ​

6.1 增长对比表（n 从小到大） ​

6.2 数据规模与可承受复杂度速查 ​

七、分析易错点 ​

7.1 嵌套循环不等于 n² ​

• 只有内层完整跑 n 次才是 n²；若内层随外层缩小（j 从 i 开始）仍是 n²/2 = O(n²)。
• 错误示范：看到两个 for 就写 O(n²)，没注意内层是 for j in range(k)（k 为常数）→ 实际 O(n)。

7.2 递归树漏算 ​

• 易错一：只算「一棵子树」忽略指数爆炸（朴素斐波那契是 2ⁿ 不是 n²）。
• 易错二：忘记每一层都要扫描，如快排每层分区 O(n)、共 log n 层，平均 O(n log n)。

7.3 字符串操作的隐藏复杂度 ​

• Java 中 String 不可变，循环里 s += c 每次都新建字符串 → 总 O(n²)。
• 正确做法：Java 用 StringBuilder；Python 用 ''.join(list) 或列表收集。

7.4 忽略语言内建操作的代价 ​

7.5 把最好情况当成普遍情况 ​

• 例：哈希表「理论最坏 O(n)」常被忽略；退化输入（大量哈希冲突）确实会拖慢。
• 二分查找前提是有序；没排序先排序就是 O(n log n) + O(log n) = O(n log n)。

7.6 复杂度与"实际快慢"的误区 ​

• O(10⁹) 与 O(2·10⁹) 都是 O(n) 量级，但常数影响在线评测里可能决定超不超时。
• 面试进阶话术：分析复杂度后补一句「瓶颈在内存访问模式/常数」，体现工程意识。