知识卡片
倍增扩容摊薄追加成本
动态数组满时按固定倍数扩大,再搬移旧元素,单次扩容需要线性工作;由于容量增长后能容纳许多次普通追加,连续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