知识卡片
均摊分析看一串操作成本
动态数组追加偶尔需要迁移已有元素,单次最坏可达线性,但过度分配使一串追加的平均到每次成本为常数阶,即均摊O(1)。这不同于对随机输入分布取平均。字典平均查找常数也不表示所有键、哈希计算和极端碰撞都无成本,应明确实现与操作假设。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第12章 优化——一些强大的技术 12.1.2 大O记法 · 查看原书依据
如果我们评估一系列操作的复杂度
参考来源
- 位置:《Python编程精进(第1辑)(套装共3册)(异步图书)》Python高级编程(第2版) · 第12章 优化——一些强大的技术,spine021单元004;来源项目book-sources,extracted/Python编程精进(第1辑)(套装共3册)(异步图书)/_epub-src/OEBPS/text00020.html。
- 结论依据:原文一串动态数组追加分摊偶发扩容,直接支持总工作平均到每次的分析,不等于按随机输入分布求期望。未在本机运行示例或改变环境。
- 原始内容:种实现方式可以减轻偶尔重新分配的复杂度。如果我们评估一系列操作的复杂度,我们将看到 list.append() 的平均复杂性是O(1),这实际上是一个很棒的结果。 当解决问题时,我们通常会知道很多关于输入数据的细节,例如它的大小或统计分布。