先看一整串操作
同一种接口的每次调用,成本可能相差很大。动态数组通常只需在末尾写入一个元素,容量耗尽时却要分配新数组并搬移已有内容。只用最昂贵的一次描述所有调用,可能掩盖这类昂贵操作不能连续任意发生的结构。
摊还分析先限定允许的初始状态和操作,再证明任意一串符合条件的调用,其总成本不超过某个界限。把这个界限按操作数分摊,就能描述长序列的资源需求,而不必声称每一步成本都相同。
参考:[1]
扩容次数与复制总量
若数组满时把容量翻倍,先前复制的元素数按1、2、4等规模增长。这些复制量相加仍与最后的容量处在同一数量级;从空结构开始连续追加n个元素,扩容工作因而可以由O(n)总成本覆盖。
在通常把单个元素或引用的处理视为常数成本的模型下,这给出末尾追加O(1)的摊还界。实际发生扩容的那一次仍可能是O(n),因此需要限制单次停顿的应用,不能把摊还常数时间直接读成每次都有固定延迟。
参考:[1]
保证依赖操作与策略
分摊结论必须与实际策略相配。若容量每次只增加一个位置,反复追加就可能一再复制几乎全部内容;若删除后立即缩小到刚好容纳元素,插入和删除交替也可能频繁搬移。增长和收缩的间隔是分析的一部分。
这种“平均”不等于在随机数据上的期望。它针对符合假设的整段操作序列作界定,也不把数组中间插入所需的元素移动消除掉。比较算法时,应同时说明单次最坏界、摊还界与采用的操作模型。