知识卡片

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

平均常数不是最坏保证

理解等级:中级

散列表在合理散列及负载条件下,查找、修改和删除平均可接近O(1),大量冲突时最坏可到O(n),用户自定义hash与相等计算也另有成本。原书“平摊最坏”表头易混淆平均、摊销与单次最坏分析,应分别说明假设。不能因容器名为dict就保证任何输入和键类型都恒定耗时。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《Python编程精进(第1辑)(套装共3册)(异步图书)》Python高级编程(第2版) · 第2章 语法最佳实践——类级别以下,spine011单元005;来源项目book-sources,extracted/Python编程精进(第1辑)(套装共3册)(异步图书)/_epub-src/OEBPS/text00010.html。 - 结论依据:原文复杂度表同时给平均O(1)与最坏O(n),支持两种分析前提分开;“平摊最坏”表头未被当作统一保证。未在本机运行示例或改变环境。 - 原始内容:本操作(添加元素、获取元素和删除元素)的平均时间复杂度为O(1),但它们的平摊最坏情况复杂度要高得多,为O(n),这里的n是当前字典的元素数目。此外,如果字典的键是用户自定义类的对象,并且散列方法不正确的话(发生冲突的风险很大),那么