知识卡片
平均常数不是最坏保证
散列表在合理散列及负载条件下,查找、修改和删除平均可接近O(1),大量冲突时最坏可到O(n),用户自定义hash与相等计算也另有成本。原书“平摊最坏”表头易混淆平均、摊销与单次最坏分析,应分别说明假设。不能因容器名为dict就保证任何输入和键类型都恒定耗时。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第2章 语法最佳实践——类级别以下 2.1.2 集合类型 · 查看原书依据
平均时间复杂度为O(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是当前字典的元素数目。此外,如果字典的键是用户自定义类的对象,并且散列方法不正确的话(发生冲突的风险很大),那么