⏱ 算法复杂度

算法效率的衡量标准有两个核心指标：时间复杂度（运行时间）和空间复杂度（内存占用）。两者统称为算法复杂度，用大 O 记法（Big O notation）表示。

一、大 O 记法

大 O 记法用于描述算法效率随数据规模 $n$ 增长的变化趋势。它不关注精确的执行时间，而关注增长量级。

1. 核心原则：忽略常数项与低阶项

def example(arr):
    print("Hello")          # 1 次
    print("Hello")          # 1 次
    for x in arr:           # n 次
        print(x)
    for x in arr:
        for y in arr:
            print(x, y)     # n² 次

总操作数为 $2+2n+n^2$。在大 O 记法中：

• 常数项 $2$ 可以忽略
• 低阶项 $2n$ 可以忽略
• 保留最高阶项 $n^2$，记作 $O(n^2)$

2. 常见复杂度对比

大 O 记号	名称	$n=10$	$n=1000$	典型算法
$O(1)$	常数阶	1	1	数组随机访问
$O(\log n)$	对数阶	≈3	≈10	二分查找
$O(n)$	线性阶	10	1000	线性遍历
$O(n\log n)$	线性对数阶	≈33	≈10000	快速排序、归并排序
$O(n^2)$	平方阶	100	${10}^6$	冒泡排序、选择排序
$O(2^n)$	指数阶	1024	极大	暴力递归

二、时间复杂度

时间复杂度描述算法执行时间随输入规模 $n$ 增长的变化趋势。

1. $O(1)$ —— 常数阶

无论数据规模多大，执行次数恒为常数。

def get_first(arr):
    return arr[0]  # 执行 1 次

2. $O(n)$ —— 线性阶

执行次数与输入规模 $n$ 成正比。

def find_max(arr):
    max_val = arr[0]
    for x in arr:       # 循环 n 次
        if x > max_val:
            max_val = x
    return max_val

$n=100$ 时循环 100 次，$n=1000$ 时循环 1000 次。

3. $O(n^2)$ —— 平方阶

常见于双层嵌套循环，每层遍历规模均为 $n$。

def print_pairs(arr):
    for i in arr:         # n 次
        for j in arr:     # n 次
            print(i, j)   # n² 次

4. $O(\log n)$ —— 对数阶

每轮操作将问题规模减半，执行次数为 ${\log }_{2}n$。

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

当数组有 1024 个元素时，二分查找最多执行 ${\log }_{2}1024=10$ 次。

5. $O(n\log n)$ —— 线性对数阶

常见于高效排序算法。将数据递归拆分，每层需遍历一次。

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)  # 合并操作 O(n)

6. $O(2^n)$ —— 指数阶

每增加一个输入规模，工作量翻倍。效率极低，仅适用于极小规模数据。

def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-1)  # 每次调用分裂为两个

计算 $\text{fib}(30)$ 约需 10 亿次函数调用，实际工程中应避免此类实现。

三、空间复杂度

空间复杂度描述算法运行时额外占用的内存空间随 $n$ 的变化趋势。注意：通常只计入辅助空间，输入数据本身占用的空间不计。

1. $O(1)$ —— 常数空间

仅使用固定数量的变量，与 $n$ 无关。

def sum_array(arr):
    total = 0          # 仅一个变量
    for x in arr:
        total += x
    return total

2. $O(n)$ —— 线性空间

额外分配的空间与 $n$ 成正比。

def duplicate(arr):
    result = []
    for x in arr:
        result.append(x)  # 复制一份等长数组
    return result

3. $O(n^2)$ —— 平方空间

常见于 $n\times n$ 矩阵等场景。

def create_matrix(n):
    matrix = []
    for i in range(n):
        matrix.append([0] * n)  # n × n
    return matrix

四、分析示例：冒泡排序的复杂度

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        for j in range(n - i - 1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

第1步：确定核心操作

• 比较操作：arr[j] > arr[j+1]
• 交换操作：arr[j], arr[j+1] = arr[j+1], arr[j]

第2步：统计执行次数

外层循环 $i$ 从 $0$ 到 $n-2$，共 $n-1$ 轮。第 $i$ 轮内层循环执行 $n-i-1$ 次。

总比较次数为：

$$(n-1)+(n-2)+\cdots +1=\frac{n(n-1)}{2}$$

第3步：取最高阶

$$\frac{n(n-1)}{2}=\frac{n^2}{2}-\frac{n}{2}$$

忽略常数 $\frac{1}{2}$ 和低阶项 $\frac{n}{2}$，得到 $O(n^2)$。

第4步：分析空间复杂度

冒泡排序为原地排序，仅使用 $n,i,j$ 等固定变量，未分配额外数组。空间复杂度为 $O(1)$。

五、时间与空间的权衡

时间复杂度和空间复杂度往往不可兼得，需根据实际场景取舍。以"判断数组中是否存在重复元素"为例：

方法 A：暴力双循环（以时间换空间）

def has_duplicate(arr):
    n = len(arr)
    for i in range(n):
        for j in range(i + 1, n):
            if arr[i] == arr[j]:
                return True
    return False

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(1)$

方法 B：哈希集合缓存（以空间换时间）

def has_duplicate(arr):
    seen = set()
    for x in arr:
        if x in seen:
            return True
        seen.add(x)
    return False

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

现代计算机内存成本较低，实际开发中通常优先选择时间复杂度更优的实现。

六、总结

复杂度速查表

复杂度	含义	典型算法
$O(1)$	与输入规模无关	数组随机访问
$O(\log n)$	每轮减半	二分查找
$O(n)$	与输入规模成正比	线性遍历
$O(n\log n)$	拆分后线性处理	归并排序、快速排序
$O(n^2)$	双重循环	冒泡排序、选择排序
$O(2^n)$	每增一数据工作量翻倍	暴力递归

分析方法

1. 分析循环：单层循环通常为 $O(n)$，双层循环通常为 $O(n^2)$
2. 分析递归：每次减半为 $O(\log n)$，每次分裂为两个为 $O(2^n)$
3. 分析辅助空间：未使用额外数组为 $O(1)$，复制输入数据为 $O(n)$
4. 忽略常数项和低阶项：$3n^2+100n+1000$ 仍为 $O(n^2)$