动态阵列是数据结构,在达到容量后自动调整大小。了解其摊余成本有助于评价其对于多个操作的效率。

什么是摊销成本?

摊余成本是一系列业务中每次业务的平均成本,通过在许多廉价业务中分配,平缓了偶尔再调整成本的高昂问题。

动态矩阵操作

动态阵列上常见的操作包括插入,删除,以及重排大小. 插入端通常是最频繁的操作,在超过容量时可能会触发重排大小.

计算摊余费用

插入元素时, 数组在满时大小会翻倍。 重排成本涉及将所有现有元素复制到新数组。 尽管重排成本很高, 但不会经常发生 。

例如,如果一个阵列从容量1开始,那么在多次插入后对成本进行再调整的顺序可以归纳为:

  • 插入1项内容:费用1
  • 插入第2项:调整规模(费用1),总费用2
  • 插入第3项:调整规模(费用2),总费用3
  • 插入第4项:调整规模(费用4),总费用4

n插入的总成本与2n成比例,使每次插入的摊余成本约为O(1).