删除操作 思考 当动态表的实现 (mum,+1)+(size, /2-num )-(size-/2-num-j) 1.考虑该表地址查找频繁 2.考虑该表地址查找稀少 (nm+1)+(mm2+1)-nm2)-(2nm+2)-(nm2+1) 总结 →分摊分析把一个系统作为整体考虑,有 种常用方法 聚集 做账 统筹安排——另一种设计思路: 利用提高某些操作的成本,来达到减少其它操 作成本,最后达到整体操作成本最优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 总结 分摊分析把一个系统作为整体考虑，有三 种常用方法： 聚集 做账 势 统筹安排——另一种设计思路： 利用提高某些操作的成本，来达到减少其它操 作成本，最后达到整体操作成本最优