知识卡片

普通读书笔记卡 · 1708.b.3.f · 生成模型:未记录

期望成本按概率加权一次

理解等级:中级

若规模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个元素的平均情况为: