O(log n)

一句话理解

O(log n) 每次把问题缩小成几分之一。

为什么要学

二分查找、快速幂、倍增跳跃。

讲解

n=1e9 时 log2 n 大约 30，非常快。

若写成 while(n) n/=2，循环次数就是对数级。

例子

int cnt = 0;
while (n) { n /= 2; cnt++; }

n 反复折半，次数约 log n。

记住：对数级对 1e18 也只是 60 左右。

常见错误

• 对数底数在复杂度记号里通常忽略。
• n=0 的边界。