O(n方) 有多慢 · 考级冲刺

两层嵌套循环，外层跑 $n$ 次、内层每次也跑 $n$ 次，总操作约 $n \times n = n^{2}$ ，记作 $O (n^{2})$ ，即"平方时间"。数据一大，它增长得很凶。

// 冒泡排序：典型 O(n^2)
for (int i = 0; i < n - 1; i++)
    for (int j = 0; j < n - 1 - i; j++)
        if (a[j] > a[j+1]) swap(a[j], a[j+1]);

$n = 1000$ 时约 $1 0^{6}$ （一百万）次，还能接受；但 $n = 1 0^{5}$ 时就是 $1 0^{10}$ ，远超一秒能算的 $1 0^{8}$ ，必然超时。

冒泡、选择、插入排序，以及"两两配对枚举"都是 $O (n^{2})$ 。判断能不能用它，直接看数据范围： $n \leq 5000$ 左右一般可以，上万就危险。坑：即便内层只跑半程（如上面的 n-1-i），总次数约 $n^{2} /2$ ，量级仍是 $O (n^{2})$ ，常数减半救不了，这时要想办法换成 $O (n lo g n)$ 或 $O (n)$ 的做法。