知识卡片

普通读书笔记卡 · 1709.c.1

几何扩容摊薄复制成本

理解等级:中级

动态数组满时按固定比例扩大,复制成本形成几何级数,其总量仍与最终元素数同阶,所以连续追加可获得摊销常数成本。比例小会更频繁复制、减少闲置空间;比例大则相反。单次扩容依然可能复制大量元素,[[摊销看长期成本]]不能当成每次延迟都固定的保证;这里讨论追加而非任意位置插入。

缩容也需留出滞后区间:刚扩容后若一次删除就缩回,反复插入和删除会反复复制。书中练习据此把缩容阈值与满容量分开,保证两次昂贵调整之间有足够多普通操作。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 3 处

    参考来源

    - 位置:《你真的会写代码吗-2021》第3章《速度的要求:时间效率》(来源项目book-sources:`extracted/你真的会写代码吗-2021/_epub-src/OEBPS/Text/0013.xhtml`) - 结论依据:原文以“将数组扩大任意百分比(包括微不足道的10%)都会导致插入的摊销复杂度为常数时间”所在的机制、例子或限制条件支撑本文;适用边界及读者推导在正文中单独说明。 - 原始内容:将数组扩大任意百分比(包括微不足道的10%)都会导致插入的摊销复杂度为常数时间。为了证明这一点,只需将3.3.5节中计算使用的扩容因子1.5替换为另一个扩容因子,比如1.1(代表10%)。 选择正确的 - 补充来源:第 3 章 速度的要求:时间效率,3.3 最好的平衡:并查集算法(Speed3);`extracted/你真的会写代码吗-2021/_epub-src/OEBPS/Text/0013.xhtml`。 - 补充来源:第 3 章 速度的要求:时间效率,3.9 小测验答案和练习答案;`extracted/你真的会写代码吗-2021/_epub-src/OEBPS/Text/0013.xhtml`。