大 O 的误用：常数和前提比阶更常决定成败

拿大 O 比较两个实现，只在同一个数量级区间内成立。出了那个区间，常数、内存局部性、分支预测的影响会大过阶本身。

小 n 时低阶算法赢

插入排序是 O(n²)，快速排序是 O(n log n)。但 n = 10 时插入排序通常更快：没有递归、没有分区开销、顺序访问数组。

标准库的排序普遍这么做：小数组切到插入排序，大数组才走快排。

n = 10     插入排序快 2 倍
n = 1000   快排快 20 倍

所以「O(n²) 一律不能用」是错的。要先问 n 的实际上界。

O(1) 不意味着快

哈希表查找是均摊 O(1)，数组线性扫描是 O(n)。n = 8 时数组往往更快：一次缓存行读取对比哈希计算加探测。

更极端的例子是链表——理论上 O(1) 的插入，实际因为每次都要跳指针，遍历起来比数组慢一个数量级。大 O 完全不描述内存布局。

前提条件才是关键

哈希表 O(1) 的前提是哈希均匀。攻击者可以构造大量碰撞的键，把查找退化成 O(n)。这不是理论问题，是拒绝服务漏洞的常见来源。

数据结构	声称	前提
哈希表	O(1)	哈希均匀且不可预测
快排	O(n log n)	平均情况，枢轴选得好
动态数组追加	均摊 O(1)	扩容按倍数增长
B-tree 查找	O(log n)	键分布不极端偏斜

怎么实际比较

1. 先量再优化。 没有 profile 的优化是在猜。
2. 用真实数据规模。 十万条和十条的结论可能相反。
3. 看常数。 同一阶的两个实现差 5 倍很常见。
4. 看内存。 缓存未命中往往比多几次算术更贵。

大 O 回答的是「数据翻倍时慢多少」，不是「哪个更快」。两个问题别混。