知识卡片

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

倍增扩容摊薄追加成本

理解等级:中级

动态数组满时按固定倍数扩大,再搬移旧元素,单次扩容需要线性工作;由于容量增长后能容纳许多次普通追加,连续n次追加的总搬移量可受几何级数控制,形成均摊常数成本。

均摊不是每次都常数,也不是随机输入下平均。原书倍率2是教学选择,实际容器增长策略和append是否复用旧容量依实现,不是Go语言承诺。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      每次将数组扩容至之前的2 倍。 // === File: my_list.go === /* 列表类 */ type myList struct { arrCapacity int arr [] int arrSize

    参考来源

    - 位置:《Hello 算法--Go版本》第04章《数组与链表》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/2.html;spine 1,归一字符[25972,26081)) - 结论依据:实际myList容量/size/扩容机制及末尾非每次O1问答,解释均摊前提不把2倍当标准规则。 - 原始内容:每次将数组扩容至之前的2 倍。 // === File: my_list.go === /* 列表类 */ type myList struct { arrCapacity int arr [] int arrSize