← 返回刚才阅读的位置

知识卡片

普通读书笔记卡 · 470.b.1.a.1.c.3.a.6.a.2.d.1.a.1.a.1.a.5.a.1.b.1

几何扩容摊薄总复制成本

理解等级:中级

若每次容量不足就近似翻倍,连续追加n项时复制量形成1+2+4等几何和,总量为O(n),所以单项摊销O(1)。一次触发扩容的追加仍需复制很多元素,并非每次都常数时间。这个结论依赖增长策略和连续追加模型,还以额外预留空间为代价。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《Go语言圣经》第04章《Slice》(来源项目book-sources:extracted/Go语言圣经/_epub-src/ch4-02.html;spine 34,归一字符[5174,5202)) - 结论依据:原文appendInt翻倍与均摊说明支持几何和推导,正文区分单次与摊销。 - 原始内容:通过在每次扩展数组时直接将长度翻倍从而避免了多次内存分配