知识卡片
动态表收缩摊还常数
删除使装载率低于四分之一时,缩半并复制剩余元素虽有线性实际成本,但此前从半满降到四分之一的删除已积累势能。收缩时势能下降抵销搬迁,原文逐情形得到插删操作的摊还成本均有常数上界。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第16章 摊还分析 · 查看原书依据
Therefore, when the ith operation is a deletion that triggers a contraction, its amortized cost is ĉi = ci + ΔΦi = sizei−1/4 + (1 − sizei−1/4) = 1.
参考来源
- 位置:《算法导论(第4版)》第16章《摊还分析》(OEBPS/chapter016.xhtml,文本字符[45000,50000))。
- 结论依据:16.4.2 节收缩前 Φ=旧容量/4,恰可覆盖删除与复制成本;收缩后 Φ=1,所以 ĉ=c+ΔΦ=1,其他插删分支也有常数摊还界。
- 原始内容:Therefore, when the i th operation is a deletion that triggers a contraction, its amortized cost is ĉ i = c i + ΔΦ i = size i −1 /4 + (1 − size i −1 /4) = 1.