7.6 本章归纳总结
原书定位
印刷页P336起,对应PDF第348页。下文为目视整理的知识提要;完整内容见原书对照。
所有 ASL 都先列样本、概率与比较次数,再求加权和。分别讨论成功和失败时,各自概率和为 1;若混合讨论,需再给成功与失败的总体概率。不要把记录数、失败间隙数、散列地址数混作同一个分母。
选择结构时同时考虑查询、更新、内外存与访问方式。静态有序数组适合折半;频繁动态更新可考虑平衡搜索树;外存多路索引用 B 树或 B+ 树;不依赖顺序的键查询可用散列表。
思维拓展的多数元素可用两两抵消:不同元素相互抵消,剩余候选用一次复查确认出现次数是否超过一半,总时间 、辅助空间 。
关联知识
原书对照
展开原书对照截图
