复杂度与数据规模复杂度与数据规模

专题导读

复杂度不是为了给代码贴标签，而是用输入规模预测程序是否能在时间与内存限制内完成。面试中应先根据 n 的范围确定复杂度上限，再选择算法；写完代码后，还要能解释最坏情况、额外空间和隐藏常数。

学习目标

• 根据数据规模快速判断可接受的时间复杂度
• 正确分析顺序、嵌套、折半和递归代码
• 区分最坏、平均、均摊复杂度以及额外空间
• 避免只看循环层数、忽略输入分布和语言开销

从数据规模倒推算法

先看约束，再想算法。下面是竞赛与面试环境中的经验值，不是严格边界，但足以用于第一轮方案筛选。

通常可以把 1 秒内可执行的简单操作粗略估算为 10⁷ 到 10⁸ 次。Java 代码还会受到 JIT 预热、自动装箱、对象分配、GC 与集合常数开销影响，因此复杂逻辑应保守估计。

当 n 达到 10⁵ 时，O(n²) 几乎一定不可行；当 n 只有 20 左右时，2ⁿ 的状态枚举反而可能是正确方向。

输入规模与常见复杂度上限

判断顺序： 数据规模 → 时间上限 → 候选复杂度 → 数据特征 → 具体算法。不要先套模板，再回头验证是否超时。

渐进复杂度的计算规则

Big-O 关注 n 增大时的增长趋势，因此忽略常数项和低阶项，但不能忽略不同变量。

顺序执行取最大项

O(n) + O(n log n) + O(1) 最终记为 O(n log n)，因为高阶项主导增长。

嵌套循环通常相乘

两层都遍历 n 次是 O(n²)；若内层只遍历到 i，总次数为 1+2+…+n，仍是 O(n²)。

指针单调移动看总次数

双指针即使写成 while 套 while，只要左右指针都不回退，总移动次数通常是 O(n)，不是 O(n²)。

规模每次减半是对数

二分查找、堆高度以及不断执行 n = n / 2 的循环，迭代次数为 O(log n)。

多个输入变量分别保留

遍历两个独立数组应写 O(n + m)，不能在没有关系时简化成 O(n)。

均摊分析与隐藏成本

单次操作很贵，不代表一系列操作都很贵。均摊复杂度把偶发的扩容或清理成本分摊到整个操作序列。

ArrayList 容量不足时会申请更大数组并复制已有元素，某一次 add 是 O(n)，但容量按比例增长时，连续 n 次 add 的总复制量仍为 O(n)，因此平均每次是 O(1)。

哈希表查询通常写作平均 O(1)，但极端冲突下可能退化。面试表达时应说明依赖良好的哈希函数、合理负载因子和扩容策略。

动态数组扩容

单次最坏 O(n)，连续追加的均摊复杂度 O(1)。

单调栈

元素可能在 while 中连续出栈，但每个元素最多入栈、出栈各一次，总复杂度 O(n)。

路径压缩并查集

单次操作不是严格 O(1)，多次操作的均摊复杂度接近常数。

不要因为循环体中有两个指针就判断为 O(n²)。关键是统计每条语句在整个执行过程中最多发生多少次。

public final class SortedArrayDeduplicator {
    private SortedArrayDeduplicator() {
    }

    public static int removeDuplicates(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int slow = 0;
        // fast 只向右移动一次；slow 也从不回退
        for (int fast = 1; fast < nums.length; fast++) {
            if (nums[fast] != nums[slow]) {
                nums[++slow] = nums[fast];
            }
        }
        return slow + 1;
    }
}

// 时间 O(n)，额外空间 O(1)

空间复杂度与递归栈

空间复杂度通常分析相对输入规模新增的辅助空间，不把输入和返回结果本身重复计算，但应主动说明口径。

额外数据结构

长度为 n 的哈希表、前缀和数组或 visited 数组都是 O(n) 辅助空间。

递归调用栈

递归深度为 h，就会占用 O(h) 栈空间；退化二叉树的 DFS 深度可能达到 O(n)。

原地算法

O(1) 额外空间不等于完全不分配内存，而是额外空间不随 n 增长。

输出空间

生成全部排列本身需要 O(n · n!) 输出；分析辅助空间时应与输出规模分开说明。

常见误区

看到两层循环就写 O(n²)

先判断内层指针是否会重置。滑动窗口、单调栈中的 while 总执行次数可能只有 O(n)。

把哈希表操作无条件当作 O(1)

应说明这是平均复杂度；最坏情况与哈希冲突、扩容实现有关。

忽略 Java 标准库的真实成本

Arrays.sort(int[]) 是双轴快速排序，平均 O(n log n)；List.subList 是视图而非复制；String.substring 在现代 JDK 中会复制字符数据。

递归只算时间，不算栈空间

递归深度可能触发栈溢出，也是空间复杂度的重要部分。

面试追问

Q1：为什么二分查找是 O(log n)？

每轮比较后搜索区间至少缩小一半。执行 k 轮后剩余规模为 n / 2ᵏ，当它降到 1 时，k = log₂n，因此是 O(log n)。

Q2：ArrayList.add 为什么是均摊 O(1)？

扩容虽需 O(n) 复制，但容量按比例增长时，插入 n 个元素产生的总复制量仍是 O(n)，所以平均到每次 add 为 O(1)。单次最坏复杂度仍是 O(n)。

Q3：如何分析递归算法复杂度？

先写出递推式，再看递归树的层数和每层工作量。例如归并排序 T(n)=2T(n/2)+O(n)，共有 O(log n) 层，每层 O(n)，所以是 O(n log n)。