← 返回刚才阅读的位置

知识卡片

普通读书笔记卡 · 1958.c.12.a.1.nv · 生成模型:未记录

均摊分析看一串操作成本

理解等级:中级

动态数组追加偶尔需要迁移已有元素,单次最坏可达线性,但过度分配使一串追加的平均到每次成本为常数阶,即均摊O(1)。这不同于对随机输入分布取平均。字典平均查找常数也不表示所有键、哈希计算和极端碰撞都无成本,应明确实现与操作假设。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《Python编程精进(第1辑)(套装共3册)(异步图书)》Python高级编程(第2版) · 第12章 优化——一些强大的技术,spine021单元004;来源项目book-sources,extracted/Python编程精进(第1辑)(套装共3册)(异步图书)/_epub-src/OEBPS/text00020.html。 - 结论依据:原文一串动态数组追加分摊偶发扩容,直接支持总工作平均到每次的分析,不等于按随机输入分布求期望。未在本机运行示例或改变环境。 - 原始内容:种实现方式可以减轻偶尔重新分配的复杂度。如果我们评估一系列操作的复杂度,我们将看到 list.append() 的平均复杂性是O(1),这实际上是一个很棒的结果。 当解决问题时,我们通常会知道很多关于输入数据的细节,例如它的大小或统计分布。