O(n log n)

一句话理解

O(n log n) 常见于排序、树状数组、线段树、堆。

为什么要学

n=1e5 的标准复杂度。

讲解

可以想成：对每个元素做一次对数级操作，或整体排序一次。

多数“比暴力快一截”的算法落在这里。

例子

sort 是 O(n log n)。n 次二分也是 O(n log n)。

常见错误

• n=1e5 再套一层 n 变成 n² log n，必 TLE。
• 忽略 log 的底和常数，极端时仍可能卡。