O(1)

一句话理解

O(1) 表示和 n 无关，常数时间。

为什么要学

公式、哈希期望、数组下标访问，都是 O(1)。

讲解

交换两个变量、读 a[i]、位运算判奇偶，都是 O(1)。

O(1) 也可以有较大常数，只是不随 n 涨。

例子

int mid = (l + r) / 2;
int x = a[i];

这两句都是常数时间。

常见错误

• 把“只写了一行”当成 O(1)，那一行若是 sort 就不是。
• O(1) 空间和 O(1) 时间搞混。