O(n)

一句话理解

O(n) 线性：每个元素处理常数次。

为什么要学

扫描数组、线性 DP、多数贪心。

讲解

n=1e6 往往能过，n=1e7 要看常数。

这是能处理大数据的基本门槛。

例子

long long s = 0;
for (int i = 1; i <= n; i++) s += a[i];

每个元素加一次，O(n)。

常见错误

• 循环里又套了一层 n 的操作，就变成 n²。
• 输入输出没加速时，O(n) 也可能慢在 IO。