知识卡片

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

扩容信用预付两类搬迁

理解等级:中级

倍增表的记账法可给每次插入收取3个成本单位:

  • 1个付当前插入,
  • 1个预付新项未来搬迁,
  • 1个预付扩容后已存在旧项的搬迁。

下次装满前足够多的新插入已发生,旧项和新项都能带着信用付复制成本。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第16章 摊还分析 · 查看原书依据

      Each call of TABLE-INSERT charges $3 as follows: $1 to pay for the elementary insertion, $1 on the item inserted as prepayment for it to be reinserted later, and $1 on an item that was already in the table

    参考来源

    - 位置:《算法导论(第4版)》第16章《摊还分析》(OEBPS/chapter016.xhtml,文本字符[30000,35000))。 - 结论依据:图16.3 的记账法每次插入收3美元:1付本次插入,1存新项、1存扩容前已有旧项,供下次扩容时再插入。 - 原始内容:Each call of T ABLE -I NSERT charges $3 as follows: $1 to pay for the elementary insertion, $1 on the item inserted as prepayment for it to be reinserted later, and $1 on an item that was already in the table