7.6 本章归纳总结

教材导航 · 第7章

原书定位

印刷页P336起,对应PDF第348页。下文为目视整理的知识提要;完整内容见原书对照。

所有 ASL 都先列样本、概率与比较次数,再求加权和。分别讨论成功和失败时,各自概率和为 1;若混合讨论,需再给成功与失败的总体概率。不要把记录数、失败间隙数、散列地址数混作同一个分母。

选择结构时同时考虑查询、更新、内外存与访问方式。静态有序数组适合折半;频繁动态更新可考虑平衡搜索树;外存多路索引用 B 树或 B+ 树;不依赖顺序的键查询可用散列表。

思维拓展的多数元素可用两两抵消:不同元素相互抵消,剩余候选用一次复查确认出现次数是否超过一半,总时间 O(n)O(n)、辅助空间 O(1)O(1)。

关联知识

原书对照

展开原书对照截图

原书对照,原书P336,PDF第348页