算法刷题系列（五十七）：算法复杂度与数据结构——如何衡量和组织

算法刷题系列（五十七）：算法复杂度与数据结构——如何衡量和组织

前 56 篇从模拟、线性结构一路走到图和动态规划。本篇把旧笔记中的“算法是什么、复杂度怎么看、数据结构如何分类”整理成一张总地图：算法规定处理步骤，数据结构组织状态，复杂度帮助我们判断组合是否适合输入规模。

理解复杂度不是为了背 O(n log n)，而是为了在写代码前做数量级估算，并知道时间和空间之间付出的代价。

一、算法与数据结构各自回答什么？

• 算法回答：输入如何经过有限步骤得到目标输出？
• 数据结构回答：状态如何组织、读取、更新，才能让这些步骤高效？

同一逻辑数据可以使用不同存储方式。例如线性表可以用连续数组或链表表示；两者保存元素顺序相同，但随机访问、插入和删除成本不同。

看数据结构时可分两层：

1. 逻辑关系：元素之间是线性、一对多还是多对多。
2. 物理表示：元素如何落在内存中，例如连续存储、节点链接或散列位置。

选择结构应从实际操作出发，而不是只按名称分类。

二、用数量级估算时间

设输入规模为 n。通常分析最坏情况下，关注主要操作执行次数的增长阶：

增长阶	常见例子	大规模输入的直觉
O(1)	数组下标访问	操作数基本不随 n 增长
O(log n)	有序区间二分	每一步把候选规模缩小
O(n)	一次扫描	每个元素访问常数次
O(n log n)	比较排序	分层处理并在每层线性合并
O(n²)	枚举所有元素对	输入翻倍，工作量约增至四倍
O(2^n)	枚举所有子集	规模稍增就可能不可行

常数、机器、语言和输入分布仍会影响实测时间；渐进复杂度主要用于比较规模扩大后的增长趋势。若 n 很小，简单的高复杂度方法可能仍足够快；若 n 很大，也要考虑内存和常数开销。

三、循环结构如何变成复杂度

单层遍历 n 个元素通常是 O(n)。两层都遍历 n 次通常是 O(n²)。若外层每次把规模减半，则层数是 O(log n)。

三段依次执行的循环，复杂度相加：

O(n) + O(n) + O(n) = O(n)

循环嵌套时，工作量相乘。若内层依赖外层次数，还要把次数求和，例如内层运行 1 + 2 + ... + n 次，仍为 O(n²)。

四、空间复杂度看“额外”状态

通常区分输入本身占用与算法额外开辟的空间：

• 只用几个计数变量：额外空间 O(1)；
• 复制长度为 n 的数组：额外空间 O(n)；
• 递归深度为 h：调用栈额外空间 O(h)；
• 图邻接表还保存 V 个顶点和 E 条边：空间 O(V + E)。

递归代码看起来短，并不代表空间为常数；每层调用都要保存返回位置和局部状态。

五、Java 与 Python：同一遍历为何是线性复杂度？

下面计算数组中偶数的数量。循环体对每个元素执行一次常数时间判断，所以时间 O(n)、额外空间 O(1)。

public class ComplexityExample {
    public static int countEven(int[] values) {
        int count = 0;
        for (int value : values) {
            if (value % 2 == 0) {
                count++;
            }
        }
        return count;
    }
}

def count_even(values: list[int]) -> int:
    count = 0
    for value in values:
        if value % 2 == 0:
            count += 1
    return count

assert count_even([2, 1, 4, 7, 8]) == 3
assert count_even([]) == 0

如果要记录所有偶数及其原始下标，输出本身最坏需要 O(n) 空间；空间复杂度分析应说明是否把返回结果计入额外空间。

六、根据操作选择数据结构

主要操作	常见候选	代价或注意点
按下标随机读取	动态数组	读取 O(1)，中间插入可能要搬移元素
两端进出	双端队列	适合队列、窗口端点维护
按键查找与计数	哈希表	平均快速，但不保证有序
保持有序并查找边界	平衡搜索树/有序数组	树支持动态更新；数组更新可能移动元素
按优先级取最值	堆	取顶 O(1)，插入/删除顶 O(log n)
区间统计或更新	前缀和、树状数组、线段树	按操作类型与是否在线选择

先列出问题需要的操作频率，再选择结构。为了只做几次查询而维护复杂平衡树，通常得不偿失。

七、复杂度分析的常见误区

1. 把 O 当成精确运行时间：它表达增长上界，不直接代表毫秒数。
2. 只分析平均情况：若输入可由外部控制，最坏情况可能更重要。
3. 忽略数据结构操作成本：例如在循环中对数组头部插入，整体可能退化到平方级。
4. 把返回数组排除后称空间 O(1)：要注明是否计算输出空间。
5. 只按代码行数估算：一行排序或哈希操作内部也有非平凡成本。
6. 忽略递归栈与复制：切片、子数组复制和递归都可能额外占内存。

小结

复杂度分析把代码操作数与输入规模联系起来；数据结构则决定这些操作要付出什么代价。面对新题，先估计规模、列出关键操作，再挑结构和算法，并同时检查时间、额外空间与边界。