复杂度分析回答的不是「程序跑几秒」，而是「输入规模 n 变大时，资源消耗按什么趋势增长」。大 O 给出增长的上界刻度，均摊分析解释动态数组这类偶尔昂贵的操作为何仍算便宜，最好/最坏/平均则刻画同一算法在不同输入下的差异。

它解决什么问题

真实运行时间被机器、语言、缓存、数据分布层层包裹，没有可比性。复杂度分析剥离实现细节，只保留「随 n 增长的趋势」这把与机器无关的尺子：动手前用它估算可行性（n 到 10^5 时 O(n²) 约百亿次操作，必然超时），讨论方案时用它统一「快」与「慢」的语义。

核心原理

大 O 是渐进上界

f(n) = O(g(n)) 的严格含义是：存在正常数 c 和 n₀，当 n 充分大之后恒有 f(n) ≤ c·g(n)。这个定义直接推出两条化简规则：常数因子可忽略，因为 c 本来就是任意的；低阶项可忽略，因为 n 足够大后高阶项必然主导。所以 3n + 20 记作 O(n)，n²/2 + 100n 记作 O(n²)。

与大 O 并列的还有 Ω（下界）和 Θ（夹紧的精确阶）。日常说「算法是 O(n log n)」时多半实际指 Θ，这是通行惯例，但要清楚大 O 本身只承诺「不超过」。

常见阶次与估算方法

增长从慢到快的常用刻度：O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2^n) < O(n!)。估算的基本功只有几条：

  • 顺序执行的几段代码，复杂度取最大的一项；
  • 循环看迭代次数，嵌套循环看各层真实次数之积；
  • 规模每轮减半或翻倍推进，轮数是 O(log n)；
  • 递归画递归树：总代价 = 节点数 × 单节点工作量。

经典陷阱是只数循环层数。for (i) for (j = i; j < n; j++) 的内层总次数是 n(n+1)/2，确为 O(n²)；但双指针写法中左右指针各自单调前进、合计最多走 2n 步，外观像双层实为 O(n)。判断依据永远是「基本操作执行了多少次」。

递归树有两个标准样本：二分每轮只进入一个规模减半的子问题，树高 log n、每层 O(1)，总计 O(log n)；归并每层合并工作合计 O(n)、共 log n 层，总计 O(n log n)。反例是朴素递归斐波那契：每个节点裂成两个子调用且大量重复，节点数逼近 2^n；加记忆化让每个状态只算一次，直接降到 O(n)。

深入机制

空间复杂度：别忘了调用栈

空间复杂度只统计随输入增长的额外空间，输入本身不计入。固定变量是 O(1)，长度为 n 的辅助数组是 O(n)。最易漏算的是递归：哪怕没 new 任何容器，深度为 n 的递归也占 O(n) 栈帧——迭代反转链表 O(1) 空间，递归版 O(n)，差别全在调用栈。输出占的空间是否计入，口径不一，主动说明即可。

均摊分析：动态数组为什么敢称 O(1)

ArrayList 这类动态数组在容量耗尽时翻倍扩容，单次 add 触发扩容要整体搬迁旧元素，那一刻是实打实的 O(n)。但把眼光拉长到一段连续操作：从空数组开始连加 n 个元素，扩容只在容量为 1、2、4、…、n/2 时发生，搬迁总量 1 + 2 + 4 + … + n/2 < n，再加上 n 次写入本身，总代价不超过 3n，平摊到每次 add 就是 O(1)。

class SimpleArrayList {
    private int[] data = new int[4];
    private int size = 0;

    public void add(int x) {
        if (size == data.length) {            // 满了：翻倍扩容
            int[] next = new int[data.length * 2];
            System.arraycopy(data, 0, next, 0, size);
            data = next;
        }
        data[size++] = x;                     // 常态：O(1) 写入
    }
}

倍增不是随意的：若每次只把容量加 1，每次 add 都要搬迁，总代价 1 + 2 + … + n = O(n²)，均摊退化为 O(n)。要义是让昂贵操作足够稀少，稀少到能被大量廉价操作吸收。注意均摊与概率无关——输入再恶劣，这个 O(1) 也成立。

最好、最坏与平均

三者回答的问题不同：最好情况只对应最顺手的输入，参考意义有限（插入排序在近乎有序数组上 O(n) 是少数例外）；最坏情况是对任意输入的保证，是选型底线；平均情况按输入概率加权，最接近日常体感。快排是标准样本：划分均衡时平均 O(n log n)，每次划分极端失衡（已排序数组配固定 pivot）则退化成 O(n²)。哈希表查询平均 O(1)，全冲突时退化 O(n)——这正是 JDK 8 给 HashMap 加树化兜底的原因。

工程实践

  • 用数据范围反推可用阶次：n ≤ 20 可指数级回溯；n ≤ 1000 容得下 O(n²)；n ≤ 10^5 要 O(n log n) 以内；10^6 以上基本只剩线性。先算账再动手，避免写出注定超时的实现。
  • 警惕常数与隐藏成本：String 拼接一次是 O(n)，装箱拆箱、哈希函数质量、缓存命中率都会拉大实测差距；O(n) 算法在小 n 下输给 O(n log n) 并不稀奇。
  • 主动说明口径：输出数组是否计入空间、库函数（排序、哈希表）按平均还是最坏计，讲清楚这些再报数字，比孤立的阶次专业得多。

对比与权衡

口径 回答的问题 是否涉及概率 典型例子
最好情况 最顺的输入多快 否 插入排序近有序 O(n)
最坏情况 任意输入的保证上界 否 快排退化 O(n²)
平均情况 输入按分布加权的期望 是，对输入而言 快排 O(n log n)
均摊 一段操作序列的平均成本 否，对操作而言 动态数组 add O(1)

平均与均摊最易混淆：前者的随机性来自输入分布，后者针对确定的操作序列、把偶发高成本平摊掉，不依赖运气。

面试视角

为什么复杂度分析可以忽略常数和低阶项？ 因为大 O 的定义里常数 c 任意、且只在 n 充分大后生效，低阶项终将被高阶项盖过。它是增长趋势的度量，从来不是耗时的精确公式。

O(n) 一定比 O(n log n) 快吗？ 渐近意义下成立，但 n 小或常数悬殊时未必，实测结论要跑过才知道。

递归算法的空间复杂度怎么算？ 看调用栈的最大深度乘每层帧的大小。树高 log n 的二分递归占 O(log n) 栈空间，深度为 n 的递归就是 O(n)，与是否显式分配内存无关。

动态数组单次 add 明明可能 O(n)，凭什么说是 O(1)？ 那是均摊口径：翻倍扩容的搬迁总量被 n 次廉价写入吸收，连续 n 次 add 总代价 O(n)。它不做概率假设，但保证的是一段序列而非单次操作。

快排如何避免最坏情况？ 随机选 pivot 或三数取中让极端划分的概率极低；工程实现（如 IntroSort）在递归过深时切换堆排序，用稳定的 O(n log n) 给快排兜底。

小结

  • 大 O 是渐进上界：忽略常数与低阶项是定义的直接推论，不是偷懒。
  • 估算抓两头——基本操作的执行次数定时间，随输入增长的额外存储（含调用栈）定空间。
  • 均摊分析针对操作序列：动态数组靠「翻倍让扩容足够稀少」把 add 压到均摊 O(1)。
  • 最好/最坏/平均是三种口径，谈复杂度时先声明口径，再报阶次。