删除操作:∝1≥1/2 思考 啼动态表的实现: 1.考虑该表地址查找频繁 2.考虑该表地址查找稀少 总结 中分摊分析把一个系统作为整体考虑,有三 种常用方法 聚集 团做账 团势 统筹安排—另一种设计思路 团利用提高某些操作的成本,来达到减少其它操 作成本,最后达到整体操作成本最优。8 清华大学 宋斌恒 43 删除操作： αi ≥1/2 1 ˆi = i + Φi − Φi− c c ( 1) ( / 2 ) ( / 2 ) = i + + i − i − i−1 − i−1 num size num size num = ( +1) + (( +1) − ) − ((2 ⋅ + 2) − ( +1)) numi numi numi numi numi = 1. 清华大学 宋斌恒 44 思考 动态表的实现： 1. 考虑该表地址查找频繁 2. 考虑该表地址查找稀少 清华大学 宋斌恒 45 总结 分摊分析把一个系统作为整体考虑，有三 种常用方法： 聚集 做账 势 统筹安排——另一种设计思路： 利用提高某些操作的成本，来达到减少其它操 作成本，最后达到整体操作成本最优