知识卡片
扩容信用预付两类搬迁
倍增表的记账法可给每次插入收取3个成本单位:
- 1个付当前插入,
- 1个预付新项未来搬迁,
- 1个预付扩容后已存在旧项的搬迁。
下次装满前足够多的新插入已发生,旧项和新项都能带着信用付复制成本。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 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