复杂度：为什么要估

复杂度是用来预测“程序跑多久”的尺子。我们不数具体多少毫秒，而是看运算量随数据规模 $n$ 怎么增长，记作大 $O$。$O(n)$ 表示运算量和 $n$ 成正比，$O(n^2)$ 表示 $n$ 翻倍时间就变四倍。

为什么必须先估？因为考试机一秒只能做约 $10^8$ 次运算。同一道 $n=10^5$ 的题：

// O(n^2): 10^10 次, 超时
for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) work();

// O(n log n): 约 1.7*10^6 次, 轻松通过
sort(a, a + n);

代码可能都是对的，但一个能过、一个超时。所以拿到题先看 $n$ 的范围，反推允许的复杂度，再决定用什么算法。

常见坑：大 $O$ 忽略常数，但常数太大（比如里面套了 map、字符串拷贝）也可能被卡；估算时要把循环体里真正花时间的操作也算进去。