知识卡片

普通读书笔记卡 · 3629.d.2.a.1.a

动态表收缩摊还常数

理解等级:高级

删除使装载率低于四分之一时,缩半并复制剩余元素虽有线性实际成本,但此前从半满降到四分之一的删除已积累势能。收缩时势能下降抵销搬迁,原文逐情形得到插删操作的摊还成本均有常数上界。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 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.