数据结构与算法 / 系统课时

最好最坏与平均情况

最好最坏与平均情况

同一算法处理相同长度的输入,成本也会不同。线性查找会在第一次匹配时返回。本课用元素比较次数区分最好、最坏和按分布计算的期望成本。

学习目标

  • 确定计数对象及固定规模下的取值范围。
  • 从首次命中位置和未命中概率计算期望。
  • 区分输入随机、算法内部随机以及单次运行的保证。

最好和最坏取决于合法输入

把一次“当前元素是否等于目标”计作一次比较。对长度 n≥1n≥1 的数组,首位命中只比较一次;首次命中在最后一位或完全未命中要比较 nn 次。因此在允许这些输入的定义域内,最好为 Θ(1)\Theta(1),最坏为 Θ(n)\Theta(n)。空数组的元素比较数是 0,但完整函数仍要执行返回等步骤。比较次数也不等于在任意硬件上的实测延迟。 MIT《计算机科学的数学》算法成本与概率

平均需要概率模型

若保证命中,并且首次匹配位置在 1 到 nn 之间均匀分布,则期望比较次数是 (1+2+…+n)/n=(n+1)/2(1+2+…+n)/n=(n+1)/2。若未命中概率为 qq,在命中条件下首次位置仍均匀,则期望为 qn+(1−q)(n+1)/2qn+(1-q)(n+1)/2。这两种模型下期望均为 Θ(n)\Theta(n)。若查询总命中首位,期望可为常数。 MIT《计算机科学的数学》期望

当数组各值不同,从位置中均匀抽取一个目标值会使首次命中位置也均匀。存在重复值时,抽到后一次出现的值,算法仍在第一次出现处停下。比如 [4,4,9] 从三个位置等概率抽取目标,成本分别是 1、1、3,期望为 5/35/3;若在不同值 {4,9} 中均匀抽取,期望则为 2。

实跑比较次数与分布

保存为 search_cases.py,使用 Python 3.11 或以上运行。Fraction 用于精确表示小样例概率。

python
from fractions import Fraction


def comparisons(values: list[int], target: int) -> int:
    for count, value in enumerate(values, start=1):
        if value == target:
            return count
    return len(values)


values = [4, 9, 2, 7, 5]
hit_costs = [comparisons(values, target) for target in values]
miss_cost = comparisons(values, 8)
hit_mean = Fraction(sum(hit_costs), len(hit_costs))
miss_probability = Fraction(1, 5)
expected = (1 - miss_probability) * hit_mean + miss_probability * miss_cost

repeated = [4, 4, 9]
repeated_costs = [comparisons(repeated, target) for target in repeated]
print("hit costs:", hit_costs)
print("miss cost:", miss_cost)
print("mean given hit:", hit_mean)
print("mean with misses:", expected)
print("draw by repeated positions:", Fraction(sum(repeated_costs), len(repeated_costs)))
print("empty:", comparisons([], 4))
text
hit costs: [1, 2, 3, 4, 5]
miss cost: 5
mean given hit: 3
mean with misses: 17/5
draw by repeated positions: 5/3
empty: 0

区分两种随机来源

平均情况通常对规模固定的随机输入取期望。随机算法即使固定同一输入,也可能因内部随机选择而产生不同成本,例如随机主元。报告期望时应写清是对输入取期望、对算法随机选择取期望,还是同时取期望。对每个输入的内部期望再取最大,得到最坏输入下的期望成本,它仍不是每次执行的确定上界。关心尾延迟时,还应考虑高概率界或最坏成本。 MIT《计算机科学的数学》期望与随机过程

本课练习

把未命中概率分别改为 0 和 1,核对期望落在哪两个端点。再把重复样例改为按不同值抽样,解释结果如何变化。下一课将分析不依赖概率的一段操作序列的总成本。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

最好最坏与平均情况

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通