性能

不讲数学的 Big O

一句话答案:Big O 描述「输入变大时,工作量怎么增长」。O(n) 是输入翻倍工作量也翻倍;O(n²) 是输入翻倍工作量变四倍。它描述的是形状,不是秒表。

为什么不能直接掐表

计时只告诉你这台机器这一次的情况。Big O 告诉你输入变成 10 倍时会发生什么 —— 在任何机器上。对比两种「1 加到 n」:

#include <iostream>
using namespace std;

int main() {
    int n = 10;

    // 方式一:循环 —— n 次加法
    int a = 0;
    for (int i = 1; i <= n; i++) a += i;

    // 方式二:公式 —— 永远一次乘法
    int b = n * (n + 1) / 2;

    cout << a << " " << b << endl;
    return 0;
}

答案相同,增长完全不同。方式一是 O(n);方式是 O(1) —— 常数,不管 n 多大都一样。

你真正会遇到的四种形状

Big O	名字	n 变 10 倍时	典型来源
O(1)	常数	不变	算术、数组下标
O(log n)	对数	只多一点点	每次砍一半范围
O(n)	线性	10 倍	把数据扫一遍
O(n²)	平方	100 倍	循环里套循环

数工作量,而不是计时

诀窍是把操作次数写成 n 的函数。单层循环就是 n 次:

#include <iostream>
using namespace std;

int main() {
    int n = 8;
    int steps = 0;
    for (int i = 0; i < n; i++) {
        steps++;            // 每趟一个单位的工作
    }
    cout << "n = " << n << ", steps = " << steps << endl;
    return 0;
}

现在套一层。外层每走一趟,内层都要跑满 n 次:

#include <iostream>
using namespace std;

int main() {
    int n = 8;
    int steps = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            steps++;
        }
    }
    cout << "n = " << n << ", steps = " << steps << " = n*n" << endl;
    return 0;
}

把代码里的 n 改成 4 和 16 试试:步数从 16 跳到 256。这就是平方增长,也是「对十万条数据套双重循环」会出问题的原因。

对数:砍一半

每一趟扔掉剩下范围的一半,次数就按 log₂(n) 增长:

#include <iostream>
using namespace std;

int main() {
    int n = 1000000;
    int steps = 0;
    while (n > 1) {
        n /= 2;
        steps++;
    }
    cout << "steps to shrink 1000000 to 1: " << steps << endl;
    return 0;
}

一百万只要 20 步。这就是二分查找快的原因,也是√n 判素数优于逐个试除的原因。

丢掉常数,留下形状

O(2n) 写作 O(n);O(n² + n) 写作 O(n²)。常数和较小的项会被丢掉,因为 n 很大时最大项说了算。所以两个前后相接的循环是 O(n),不是 O(n²):

#include <iostream>
using namespace std;

int main() {
    int n = 8;
    int steps = 0;
    for (int i = 0; i < n; i++) steps++;     // n
    for (int i = 0; i < n; i++) steps++;     // + n
    cout << "two separate loops: " << steps << " = 2n, which is O(n)" << endl;
    return 0;
}

这对你自己的代码意味着什么

对同一份数据套嵌套循环是 O(n²) 的常见元凶 —— 看是否存在两数之和,再想想有序数组能带来什么。
能把候选砍半就是超能力。只要你能丢掉一半可能,就进入了 log 的地盘。
预处理是划算的。区间求和用一次 O(n) 把每次提问的 O(n) 变成 O(1)。

面试追问

这段循环的复杂度是多少?数最内层语句按 n 执行多少次,再丢掉常数。
为什么排序通常是 O(n log n)?因为基于比较的排序最坏情况需要 n log n 次比较 —— 比冒泡排序的 O(n²) 好。
Big O 管内存吗?这个记号只管时间 —— 空间复杂度是另一个针对内存的 Big O。计数排序就是用空间换时间。

相关:编译错误、vector 与数组,以及题库 —— 每道题的深度解析里都写了复杂度。