数据结构与算法 / 系统课时
最好最坏与平均情况
最好最坏与平均情况
同一算法处理相同长度的输入,成本也会不同。线性查找会在第一次匹配时返回。本课用元素比较次数区分最好、最坏和按分布计算的期望成本。
学习目标
- 确定计数对象及固定规模下的取值范围。
- 从首次命中位置和未命中概率计算期望。
- 区分输入随机、算法内部随机以及单次运行的保证。
最好和最坏取决于合法输入
把一次“当前元素是否等于目标”计作一次比较。对长度 的数组,首位命中只比较一次;首次命中在最后一位或完全未命中要比较 次。因此在允许这些输入的定义域内,最好为 ,最坏为 。空数组的元素比较数是 0,但完整函数仍要执行返回等步骤。比较次数也不等于在任意硬件上的实测延迟。 MIT《计算机科学的数学》算法成本与概率
平均需要概率模型
若保证命中,并且首次匹配位置在 1 到 之间均匀分布,则期望比较次数是 。若未命中概率为 ,在命中条件下首次位置仍均匀,则期望为 。这两种模型下期望均为 。若查询总命中首位,期望可为常数。 MIT《计算机科学的数学》期望
当数组各值不同,从位置中均匀抽取一个目标值会使首次命中位置也均匀。存在重复值时,抽到后一次出现的值,算法仍在第一次出现处停下。比如 [4,4,9] 从三个位置等概率抽取目标,成本分别是 1、1、3,期望为 ;若在不同值 {4,9} 中均匀抽取,期望则为 2。
实跑比较次数与分布
保存为 search_cases.py,使用 Python 3.11 或以上运行。Fraction 用于精确表示小样例概率。
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))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,核对期望落在哪两个端点。再把重复样例改为按不同值抽样,解释结果如何变化。下一课将分析不依赖概率的一段操作序列的总成本。