O(n²)

一句话理解

O(n²) 两层 n 循环。

为什么要学

n=1000 常常可过，n=1e4 就危险，n=1e5 基本不行。

讲解

枚举所有对、简单 DP、冒泡，都是 n²。

能降到 n log n 就不要停在 n²。

例子

for (int i = 1; i <= n; i++)
  for (int j = 1; j <= n; j++)
    ;

大约 n*n 次。

常见错误

• n=5000 的 n² 大约 2.5e7，有时能过；n=1e5 的 n² 是 1e10，不能过。
• 三层误当成两层。