每个复杂性类都绘制一条曲线
绘制成本与输入大小的关系
在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²)之下。log因子为线性斜率增加一个缓慢增长的乘数。
O(N²) — 向上开口的抛物线。 斜率随N增加而增加。在N = 10：成本 = 100。在N = 100：成本 = 10,000。在N = 1,000：成本 = 1,000,000。
增长中的间隙
比率O(N²) / O(N) = N。当N增长时，抛物线和对角线之间的间隙扩大。在N = 10：10×间隙。在N = 100：100×间隙。在N = 1,000：1,000×间隙。在N = 50,000：50,000×间隙。间隙始终等于N。
计算规模差距
一个大型依赖关系图包含50,000个软件包（N = 50,000）。一个算法在O(N)时间内运行。第二个在O(N²)时间内运行。在这个N处，比率O(N²)/O(N) = N = 50,000。
对线段进行二等分
二分查找作为重复对半
包含N个元素的有序数组形成一个长度为N的线段。二分查找反复对这个线段进行二等分：
1. 指向剩余线段的中点。
2. 如果目标 < 中点：右半部分消失。在左半部分递归。
3. 如果目标 > 中点：左半部分消失。在右半部分递归。
4. 如果目标 = 中点：完成。
经过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个元素开始，每步对元素数进行对半，在log₂N步内到达1个元素。
几何：对半是一个自相似操作。每次对半产生两个看起来在结构上与整体相同的两半。递归和对数共享这种自相似性。
比较与翻倍
有序数组包含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)哈希表查找。从几何上讲：沿序列的线性遍历通过函数转化为直接投影。序列消失；函数替代它。
分析分布不良的哈希
哈希表有1,000个桶和900个元素（负载因子0.9）。一个设计不良的哈希函数将其中500个元素发送到同一个桶。