知识卡片
期望成本按概率加权一次
若规模n的离散输入集合Sn中每个输入s的概率p(s)已归一化且总和为1,期望成本为Σ{s∈S_n}p(s)t(s)。若各输入等概率,则p(s)=1/|S_n|,公式才可写为Σt(s)/|S_n|。
03143在Σt(s)p(s)外又乘1/|S_n|,与正文“概率和为1”的定义矛盾,会重复除以集合大小;例如两个等概率输入成本2与4,期望为3,额外除以2会错误得到1.5。03144的(n+1)/2仅用于先前目标存在、各位置等概率的顺序搜索例。
概率模型是分析前提,真实工作负载改变时期望也会改变;平均值不能单独证明过载概率或最坏情况下的安全性。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
概率加权。如果Pr{si}=0,那么t(si)的实际值将不会影响程序的期望运行时间。我们用Tac(n)表示算法在Sn上的平均运行时间,那么Tac(n)的增长率表示算法在平均情况下的复杂度。 回忆一下,当我们描述时间或者工作量的增长率时,我们一直忽视了常数,所以我们认为顺序搜索n个元素的平均情况为:
参考来源
- 位置:《算法技术手册》第2章《平均情况》(spine1464;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1428.html;u028-ch02-007)。
- 结论依据:28全文、03143概率加权公式与03144搜索期望实际查看,例子为读者算术推导。
- 原始内容:概率加权。如果Pr{si}=0,那么t(si)的实际值将不会影响程序的期望运行时间。我们用Tac(n)表示算法在Sn上的平均运行时间,那么Tac(n)的增长率表示算法在平均情况下的复杂度。 回忆一下,当我们描述时间或者工作量的增长率时,我们一直忽视了常数,所以我们认为顺序搜索n个元素的平均情况为: