算法复杂度分析

算法复杂度分析用于衡量算法随输入规模增长所需的资源(时间与空间),是评估算法效率的核心工具。掌握大 O 表示法有助于在编码前预判程序性能,避免在数据规模扩大时出现指数级退化。

时间与空间复杂度

时间复杂度 描述算法执行步数随输入规模 n 的增长趋势;空间复杂度 描述算法在运行过程中占用的额外存储。两者通常使用大 O 表示法,只保留最高阶项并忽略常数系数,例如 3n² + 2n + 1 记为 O(n²)。

最好、最坏与平均情况

同一算法在不同输入下表现可能差异巨大,常以三种情况描述:

• 最好情况:输入最优时的复杂度,例如有序数组的线性查找为 O(1)。
• 最坏情况:输入最差时的上界,常作为算法性能的保证,例如快速排序最坏为 O(n²)。
• 平均情况:在输入分布上的期望复杂度,常用随机化或概率分析推导,例如快速排序平均为 O(n log n)。

均摊分析(amortized analysis)用于将少数高代价操作的耗时分摊到多次低代价操作上,例如动态数组 append 偶尔扩容为 O(n),但整体均摊为 O(1)。

常见复杂度级别

按增长速度快慢排列,前者在规模增大时优势越明显:

级别	名称	典型场景
O(1)	常数	哈希表查找、数组按下标访问
O(log n)	对数	二分查找、平衡 BST 查询
O(n)	线性	数组遍历、线性查找
O(n log n)	线性对数	归并排序、快速排序平均
O(n²)	平方	冒泡排序、选择排序、嵌套循环

复杂度从 O(log n) 到 O(n²) 看似只差几个量级,当 n = 10⁶ 时,前者仅需约 20 次操作,后者却高达 10¹² 次,实际运行时天差地别。

分析示例

def sum_pairs(arr):
    n = len(arr)             # O(1)
    total = 0                # O(1)
    for x in arr:            # 循环 n 次
        total += x           # O(1)
    return total             # 整体 O(n)

def has_duplicate(arr):
    for i in range(len(arr)):     # 外层 n
        for j in range(i + 1, len(arr)):  # 内层最多 n
            if arr[i] == arr[j]:  # O(1)
                return True
    return False                   # 整体 O(n²)

第一段为线性扫描,第二段双重循环实现重复检测,后者在大规模数据下需改用哈希表 O(n) 方案。复杂度分析的目标,是在写代码时主动选择更优的结构,让程序在数据增长时仍保持可控。