最佳、最坏与平均情况
衡量算法的三种方式
每个算法的成本取决于其输入。两个相同大小的输入可能产生截然不同的运行时间。复杂度分析将这种差异的三个视角形式化。
最佳情况 — Ω（Omega）： 使算法最快完成的输入。对于N项列表上的线性搜索：Ω(1) — 目标占据第一个位置。一次比较，完成。
最坏情况 — O（Big O）： 使算法最慢完成的输入。对于线性搜索：O(N) — 目标位于列表末尾，或根本不出现。需要检查每个元素。
平均情况 — Θ（Theta）： 假设均匀分布，所有可能输入的预期成本。对于线性搜索，目标同样可能占据N个位置中的任何一个：Θ(N/2) = Θ(N)。常数1/2被舍弃，因为Theta表达紧渐进增长，而非精确系数。
为什么最坏情况占主导
系统必须处理最坏情况。平均10毫秒但偶尔需要60秒的数据库查询会产生用户可见的失败。工程师为最坏情况边界设计，以便无论输入如何，性能都保持可预测。平均情况分析在概率设置中有价值，但最坏情况分析提供了保证。
二分搜索情况分析
二分搜索仅适用于排序数组。在每一步：将目标与中点处的元素进行比较。如果目标等于中点，返回它。如果目标较小，在左半部分递归。如果较大，在右半部分递归。
每次比较都消除了一半的剩余候选项。
内存增长与时间-空间权衡
计数内存，而非操作
时间复杂度衡量算法执行的操作数。空间复杂度衡量它在输入之外分配的额外内存。两者在生产系统中都很重要：快速算法如果分配O(N²)内存将耗尽服务器。
O(1)空间： 无论N如何，常数额外内存。原地排序（例如插入排序）在原始数组内交换元素。它使用少量临时变量——无论数组有多大，都是O(1)。
O(N)空间： 内存与输入大小成比例。创建N元素数组的副本需要N个插槽。从N个字符串的列表构建哈希集存储最多N个条目。
O(N²)空间： 内存与N²成比例。为具有N个顶点的图构建N×N邻接矩阵需要N²个单元。在N = 10,000个顶点时，这是10^8个条目——对于一个简单的布尔网格来说是数百兆字节。
时间-空间权衡
算法设计中的基本操作之一：用空间换取时间，或用时间换取空间。
哈希表使用O(N)额外空间来实现O(1)查找。没有哈希表，对列表的扫描以O(1)额外空间实现O(N)查找。哈希表支付内存来购买速度。
记忆化存储先前计算的结果（O(N)或更多空间）以避免重新计算。没有记忆化的递归斐波那契以O(2^N)时间运行。使用记忆化：O(N)时间和O(N)空间。空间投资以指数方式缩小时间。
哈希字典与排序列表
比较两种策略用于计数文档中N个单词的出现次数：
策略A： 一个字典（哈希映射）。插入每个单词；增加其计数。
策略B： 维护已看到单词的排序列表；在插入前使用二分搜索检查成员资格。
摊销分析：分散成本
当偶发的昂贵操作不会破坏平均性能时
某些操作偶尔很昂贵，但在序列中的平均成本很便宜。摊销分析计算整个序列中每个操作的平均成本——而不是单个操作的最坏情况成本。
动态数组（Python列表、Java ArrayList）： 从容量1开始。满时，容量翻倍。翻倍复制所有现有元素：一次追加O(N)工作。但翻倍很少见。在N次总追加之后，发生了多少次总复制操作？
翻倍发生在大小1、2、4、8、...、N/2。复制计数：1 + 2 + 4 + ... + N/2。这是一个几何级数，在所有N次追加中共计N − 1次复制。每次追加的平均复制：(N − 1) / N < 1，因此每次追加摊销O(1)，尽管每次翻倍的最坏情况成本为O(N)。
摊销分析为什么重要
一个偶尔暂停以调整大小、重新平衡或压缩结构的系统可能看起来具有令人担忧的最坏情况单个操作。摊销分析显示警报是假的：罕见的昂贵事件由许多便宜事件支付。理解摊销成本可防止过度工程化：增加复杂性以避免仅贡献O(1)摊销的罕见O(N)操作是浪费的工作。
深入学习： unhamming课程将复杂度分析应用于生产软件中的真实缺陷。参见缺失的章节：算法复杂度&MOAD-0001：沉积缺陷。
哈希表摊销插入
哈希表开始为空，当负载因子超过0.75时容量翻倍。插入1,000个元素在容量为1、2、4、8、16、32、64、128、256、512时恰好触发10次翻倍。