Chapter 01

复杂度分析

衡量算法效率的数学语言——与机器无关的性能度量标准

为什么需要复杂度分析

假设你写了两个排序程序，在自己的笔记本上测试，程序 A 跑了 2 秒，程序 B 跑了 3 秒。能说 A 更好吗？不一定——换一台更快的服务器，两者可能都不到 0.1 秒；数据量变成一百倍，程序 A 可能需要 200 秒，程序 B 只需要 30 秒。

直接测量运行时间存在三个根本性问题：

💡

核心思想复杂度分析关注的是：当输入规模 n 增大时，算法所需资源（时间或空间）的增长趋势，而不是具体数值。

大 O 表示法

大 O 表示法（Big-O Notation）给出算法的渐进上界——在最坏情况下，随着 n 趋向无穷大，算法资源消耗的增长速率。

正式定义

若存在正实数 c 和 n₀，使得对所有 n ≥ n₀，都有 f(n) ≤ c · g(n)，则称 f(n) = O(g(n))。

✅

化简规则
1. 忽略常数系数：O(2n) 写作 O(n)
2. 只保留最高阶：O(n² + n + 5) 写作 O(n²)
3. 不同量级相加取大者：O(n) + O(log n) = O(n)

常见复杂度级别

按增长速率从慢到快排列（对算法来说，增长越慢越好）：

复杂度名称典型例子n=1000 时的操作数量级
O(1)常数数组下标访问、哈希表查找1
O(log n)对数二分查找、平衡树操作~10
O(n)线性线性扫描、一次遍历1,000
O(n log n)线性对数归并排序、快速排序（平均）~10,000
O(n²)平方冒泡/插入/选择排序、嵌套循环1,000,000
O(2ⁿ)指数暴力穷举子集、递归斐波那契≈ 10³⁰⁰
O(n!)阶乘全排列暴力枚举无法想象

O(1) — 常数时间

执行时间与输入规模无关，无论 n 是 10 还是 10 亿，操作数量不变。

def get_first(arr):
    return arr[0]  # 无论数组多长，只取一个元素

def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]  # 三步固定操作，O(1)

O(log n) — 对数时间

每次操作将问题规模减半（或缩减为固定比例）。对数增长极其缓慢，log₂(10⁹) ≈ 30。

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1   # 每次搜索空间减半
        else:
            right = mid - 1
    return -1

O(n log n) — 线性对数时间

典型代表是归并排序：将数组不断二分（log n 层），每层合并时扫描所有元素（n），总计 O(n log n)。这是基于比较的排序算法的最优下界。

O(n²) — 平方时间

def has_duplicate(arr):
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):  # 嵌套循环，O(n²)
            if arr[i] == arr[j]:
                return True
    return False

O(2ⁿ) — 指数时间

def fib_naive(n):
    if n <= 1:
        return n
    return fib_naive(n-1) + fib_naive(n-2)  # 大量重复计算！
# fib(50) 需要约 2^50 ≈ 10^15 次调用

如何计算时间复杂度

基本规则

# 示例分析
def example(n):
    total = 0                          # O(1)
    for i in range(n):                  # O(n) 次
        total += i                     # O(1)
    for i in range(n):                  # O(n) 次
        for j in range(n):             # O(n) 次
            total += i * j             # O(1)
    return total
# 总复杂度：O(1) + O(n) + O(n²) = O(n²)

递归与主定理（Master Theorem）

对于形如 T(n) = a · T(n/b) + f(n) 的递归关系（其中 a 是子问题个数，b 是规模缩减比例，f(n) 是合并代价），主定理给出三种情形：

主定理三种情形
条件结论例子
f(n) = O(n^(log_b a - ε))T(n) = Θ(n^log_b a)子问题支配
f(n) = Θ(n^log_b a)T(n) = Θ(n^log_b a · log n)归并排序：T(n)=2T(n/2)+O(n)
f(n) = Ω(n^(log_b a + ε))T(n) = Θ(f(n))合并代价支配

归并排序：T(n) = 2T(n/2) + O(n)，其中 a=2, b=2, f(n)=O(n)。n^log₂2 = n，符合第二种情形，故 T(n) = O(n log n)。

空间复杂度

空间复杂度衡量算法运行所需的额外内存（辅助空间），不包括输入数据本身。

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])   # 新建子数组 → O(n) 辅助空间
    right = merge_sort(arr[mid:])  # 递归深度 log n → 栈空间 O(log n)
    return merge(left, right)       # 总空间复杂度 O(n)
⚠️

递归栈空间不要忘记递归调用本身会消耗栈空间。一个简单的递归遍历链表，空间复杂度是 O(n) 而不是 O(1)。

最优 / 平均 / 最坏情况

同一算法对不同输入的性能可能差异巨大。以快速排序为例：

最坏情况 Ω

每次选到最小/最大值作为 pivot（如对已排序数组选第一个元素），每次只排除一个元素，退化为 O(n²)。

最坏O(n²)

平均情况

随机 pivot 平均每次将数组对半分割，递归树深度 O(log n)，每层处理 O(n)。

平均O(n log n)
📌

日常习惯平时说某算法的时间复杂度，若不加说明，通常指最坏情况（upper bound）。面试中要区分三种情况进行分析。

摊还分析

某些操作偶尔会很慢，但从长期平均来看仍然高效。摊还分析将昂贵操作的代价"摊还"到多次廉价操作上。

动态数组扩容示例

Python 的 list.append()：通常只需 O(1)，但当容量不足时需要扩容（申请 2 倍空间并复制所有元素，代价 O(n)）。

# 模拟动态数组扩容
capacity = 1
size = 0
total_cost = 0

for i in range(1, n+1):
    if size == capacity:
        total_cost += capacity   # 扩容：复制所有元素
        capacity *= 2
    total_cost += 1             # 追加：O(1)
    size += 1

# 扩容发生在 size = 1, 2, 4, 8, ... 共 log n 次
# 扩容总代价 = 1 + 2 + 4 + ... + n/2 = n-1 = O(n)
# n 次 append 总代价 O(n)，每次摊还 O(1)
✅

结论动态数组的 append 操作，摊还时间复杂度为 O(1)，尽管偶尔会触发 O(n) 的扩容。

实战：分析代码复杂度

例题 1：找数组中的第二大值

def second_max(arr):
    first = second = float('-inf')
    for x in arr:              # 一次遍历 → O(n)
        if x > first:
            second = first
            first = x
        elif x > second:
            second = x
    return second
# 时间 O(n)，空间 O(1)

例题 2：判断是否含有重复元素（两种解法对比）

# 解法一：暴力枚举 O(n²)
def contains_duplicate_v1(nums):
    for i in range(len(nums)):
        for j in range(i+1, len(nums)):
            if nums[i] == nums[j]:
                return True
    return False

# 解法二：哈希集合 O(n) 时间，O(n) 空间
def contains_duplicate_v2(nums):
    seen = set()
    for x in nums:
        if x in seen:     # 哈希查找 O(1)
            return True
        seen.add(x)
    return False

例题 3：矩阵对角线求和

def diagonal_sum(matrix):
    n = len(matrix)     # n×n 矩阵
    total = 0
    for i in range(n):  # 循环 n 次，每次 O(1)
        total += matrix[i][i]        # 主对角线
        total += matrix[i][n-1-i]   # 副对角线
    if n % 2 == 1:
        total -= matrix[n//2][n//2]  # 减去中心重复计算的元素
    return total
# 时间 O(n)，空间 O(1)  ← 注意：n 是矩阵边长，矩阵共 n² 个元素
📚

复杂度速查

数组访问O(1) 二分查找O(log n) 线性扫描O(n) 归并排序O(n log n) 嵌套循环O(n²)