每个复杂性类都画出一条曲线
在输入大小上绘制成本
在 x 轴上放入输入大小 N。将成本（操作数，时间）放入 y 轴上。每个复杂性类都产生一条独特的曲线。你可以从算法的性能曲线形状中识别出增长率。
O(1) — 平坦的水平线。 函数 f(N) = 1。无斜率。成本在 N 不变的情况下永远不会改变。哈希表查找：无论表中有 10 个元素还是 10,000,000 个元素，一次哈希计算都会跳到正确的桶。
O(log N) — 轻微向上的曲线，斜率下降。 当 N = 1,000,000 时：成本约为 20 个操作。曲线在小 N 时急剧上升，然后变得平坦。每次 N 的翻倍都会增加成本的确切单位。
O(N) — 对角直线。 斜率为 1（在渐近意义上）。成本与 N 的增长率相同。如果 N 三倍化，成本也会三倍化。
O(N log N) — 斜率略向上弯曲的更陡的对角线。 在 O(N) 之上，之下。对数因子增加了一个缓慢增长的乘数。
O(N²) — 向上开口的抛物线。 斜率随 N 生长。N = 10 时：成本 = 100。N = 100 时：成本 = 10,000。N = 1,000 时：成本 = 1,000,000。
增长的差距
O(N²) / O(N) 的比率等于 N。抛物线与对角线之间的差距随 N 增长而扩大。N = 10 时：1000×差距。N = 100 时：10000×差距。N = 1000 时：100000×差距。N = 50000 时：500000×差距。差距始终等于 N。
计算扩展差距
一个庞大的依赖图包含 50,000 个包（N = 50,000）。一个算法以 O(N) 时间运行。另一个以 O(N²) 时间运行。在这个 N，O(N²)/O(N) 的比率等于 N = 50,000。
分割线段
二分搜索作为重复的分割
一个已排序的N个元素组成的数组形成了长度为N的线段。二分搜索重复地对这个段进行分割：
1. 指向剩余段的中点。
2. 如果target < midpoint：右半部分消失。递归地在左半部分进行。
3. 如果target > midpoint：左半部分消失。递归地在右半部分进行。
4. 如果target = midpoint：完成。
在k次分割后，剩余段的长度为N / 2^k。搜索在剩余段长度等于1时结束：
N / 2^k = 1 → 2^k = N → k = log₂N
因此，在N个元素上的二分搜索最多需要进行log₂N次比较。
取半与翻倍：两者是同一曲线的反面
取半和翻倍是几何的相反面。指数曲线2^k和对数曲线log₂N是沿着y = x线的对称面。
考虑纸张折叠：一张纸开始厚度为0.1毫米。每次翻倍厚度。经过42次折叠：0.1毫米 × 2^42 ≈ 439,804公里——超过月球(384,400公里)。二分搜索执行反向：从N个元素开始，每一步将数量减半，到达1个元素，需要log₂N步。
几何：分割是自相似操作。每次分割都会产生两个相互结构完全相同的半部分。递归和对数共享这种自相似性。
比较与翻倍
一个已排序的数组包含1,048,576个元素。注意：1,048,576 = 2^20。
哈希函数作为几何映射
哈希函数作为函数
哈希表通过哈希函数将键映射到桶中：
bucket = hash(key) mod table_size
这在严格的数学意义上是一个函数：它将域（所有可能的键）映射到范围（0到 table_size − 1 的桶索引）。几何上的图像：键占据一个空间；桶占据另一个空间。哈希函数将键投影到桶索引上。
O(1) 查询 —— 直接跳转，不搜索。 哈希函数在恒定时间内计算桶索引。直接跳转到该桶。没有遍历，也没有比较循环。
负载因子。 负载因子为 0.75 时，75% 的桶至少包含一个元素。超过 0.9，碰撞增加：两个键映射到同一个桶，形成桶内的元素链。查找在长链中会退化到 O(N) 的最坏情况。
分布质量作为几何
一个良好的分布的哈希函数将键均匀地分布在所有桶中。几何上：函数的范围覆盖其编码域。每个桶接收大约 N / table_size 个键。
一个差劲的哈希函数将键聚集在少数桶中。几何上：函数的范围收缩到子集中的编码域 —— 大多数键映射到相同的几个点。剩下的桶空着。
与 MOAD-0001 的关联
将列表替换为集合解决了 MOAD-0001 的问题，因为集合内部使用哈希表。O(N) 的列表扫描 → O(1) 的哈希表查找。几何上：沿序列线性遍历转化为通过函数进行直接投影。序列消失；函数取代它。
分析不良分布的哈希
哈希表有 1000 个桶，900 个元素（负载因子 0.9）。一个糟糕的哈希函数将 500 个元素发送到同一个桶中。