知识卡片
几何扩容摊薄复制成本
动态数组满时按固定比例扩大,复制成本形成几何级数,其总量仍与最终元素数同阶,所以连续追加可获得摊销常数成本。比例小会更频繁复制、减少闲置空间;比例大则相反。单次扩容依然可能复制大量元素,[[摊销看长期成本]]不能当成每次延迟都固定的保证;这里讨论追加而非任意位置插入。
缩容也需留出滞后区间:刚扩容后若一次删除就缩回,反复插入和删除会反复复制。书中练习据此把缩容阈值与满容量分开,保证两次昂贵调整之间有足够多普通操作。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 3 处
- 第 3 章 速度的要求:时间效率 · 查看原书依据
将数组扩大任意百分比(包括微不足道的10%)都会导致插入的摊销复杂度为常数时间。为了证明这一点,只需将3.3.5节中计算使用的扩容因子1.5替换为另一个扩容因子,比如1.1(代表10%)。 选择正确的
- 第 3 章 速度的要求:时间效率 3.3 最好的平衡:并查集算法(Speed3) · 查看原书依据
在需要的时候调整其大小。不幸的是,不能在数组本身上扩容3。扩容时,类需要分配一个更大的新数组,然后将旧数组的内容复制到新数组中。这个操作的代价有多大?考虑到任何添加元素的操作都可能触发昂贵的扩容操作,那么向集合中添加新元素的最终复杂度是多少?摊销复杂度是回答这些问题的正确工具。实
- 第 3 章 速度的要求:时间效率 3.9 小测验答案和练习答案 · 查看原书依据
间。为了证明这一点,只需将3.3.5节中计算使用的扩容因子1.5替换为另一个扩容因子,比如1.1(代表10%)。 选择正确的百分比需要在时间和空间之间进行权衡。百分比越小,该常数将越大,因此时间效率越低。另外,比较保守的百分比可以节省空间,因为ArrayList的容量通常会更接近
参考来源
- 位置:《你真的会写代码吗-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`。