湖南省株洲市荷塘区仙庾镇金龙东路180号 j9julebu@www.j9.com

体育新闻

动态数组扩容时为什么复制成本不只看当前长度:机制分析第17例

2026-11-15

连续追加数据时,数组容量不足就可能需要分配更大的空间并复制旧内容。每次只增加很少容量,会频繁重复复制早已存在的元素;按比例增长通常会用更多空位换取较少复制。

先明确输入与规则

本例比较两种确定规则:容量不足时加上固定增量,或把原容量翻倍。开始容量相同,逐次追加一个元素,扩容时复制当前已有的全部元素,普通追加本身不计为复制。没有删除或缩容。

本例的独立记录

初始容量6,固定增长每次增加3,共追加38个元素。翻倍策略只在不足时乘二。

大小 | 固增容量 | 本次复制 | 累计复制 | 翻倍容量 | 本次复制 | 累计复制 1 | 6 | 0 | 0 | 6 | 0 | 0 2 | 6 | 0 | 0 | 6 | 0 | 0 3 | 6 | 0 | 0 | 6 | 0 | 0 4 | 6 | 0 | 0 | 6 | 0 | 0 5 | 6 | 0 | 0 | 6 | 0 | 0 6 | 6 | 0 | 0 | 6 | 0 | 0 7 | 9 | 6 | 6 | 12 | 6 | 6 8 | 9 | 0 | 6 | 12 | 0 | 6 9 | 9 | 0 | 6 | 12 | 0 | 6 10 | 12 | 9 | 15 | 12 | 0 | 6 11 | 12 | 0 | 15 | 12 | 0 | 6 12 | 12 | 0 | 15 | 12 | 0 | 6 13 | 15 | 12 | 27 | 24 | 12 | 18 14 | 15 | 0 | 27 | 24 | 0 | 18 15 | 15 | 0 | 27 | 24 | 0 | 18 16 | 18 | 15 | 42 | 24 | 0 | 18 17 | 18 | 0 | 42 | 24 | 0 | 18 18 | 18 | 0 | 42 | 24 | 0 | 18 19 | 21 | 18 | 60 | 24 | 0 | 18 20 | 21 | 0 | 60 | 24 | 0 | 18 21 | 21 | 0 | 60 | 24 | 0 | 18 22 | 24 | 21 | 81 | 24 | 0 | 18 23 | 24 | 0 | 81 | 24 | 0 | 18 24 | 24 | 0 | 81 | 24 | 0 | 18 25 | 27 | 24 | 105 | 48 | 24 | 42 26 | 27 | 0 | 105 | 48 | 0 | 42 27 | 27 | 0 | 105 | 48 | 0 | 42 28 | 30 | 27 | 132 | 48 | 0 | 42 29 | 30 | 0 | 132 | 48 | 0 | 42 30 | 30 | 0 | 132 | 48 | 0 | 42 31 | 33 | 30 | 162 | 48 | 0 | 42 32 | 33 | 0 | 162 | 48 | 0 | 42 33 | 33 | 0 | 162 | 48 | 0 | 42 34 | 36 | 33 | 195 | 48 | 0 | 42 35 | 36 | 0 | 195 | 48 | 0 | 42 36 | 36 | 0 | 195 | 48 | 0 | 42 37 | 39 | 36 | 231 | 48 | 0 | 42 38 | 39 | 0 | 231 | 48 | 0 | 42 最后空位:固定增长1,翻倍10。

记录中的编号只用来区分本例对象,不应与大小排名或另一组记录的身份混淆。先核对单位和边界,再跟随中间值检查结果。空结果、零值与尚未确定是不同状态;分数保留精确含义,显示小数只为方便阅读。

怎样复算

每次追加后大小不得超过容量;没有扩容时复制数为零。总复制数是每次扩容前大小的和,不是最终数组长度,也不是最终容量。扩出来但尚未使用的格子占空间,却不是需要从旧数组复制的有效元素。

把两条容量曲线和累计复制量并排记录,尤其观察刚跨过容量边界的那一步。一次追加触发大量复制,并不意味着此前每次追加都同样昂贵;反过来,单次追加很便宜也不能说明整段过程总成本低。

适用条件与限制

这是操作次数模型,不等同实际分配耗时;内存分配器、缓存和元素移动方式都会影响测量。翻倍也不一定符合所有设备的内存预算,本例只是让时间与额外空间之间的取舍可计算。

练习时可以一次只改变一个条件,比较差异从哪个步骤开始。若自己的结果不同,先核对是否采用同样的规则,再定位第一个不一致的中间状态,不要只修改最终答案。输入与运算过程需要一起保存,才能判断结论究竟适用于哪一个具体场景。