MAN*_*RMA 1 algorithm data-structures
请用一个简单的问题来解释一下
我读过一本书，据说 ArrayList 在达到极限后会翻倍，如果 ArrayList 已满，则插入 N 个元素需要 O(N) 插入时间。请通过采用几个元素的 ArrayList 来解释
摊余时间简单解释一下：
如果你执行一个操作一百万次，你并不真正关心该操作的最坏情况或最好情况 - 你关心的是当你重复该操作一百万次时总共花费了多少时间。
因此，即使操作偶尔很慢也没关系，只要“偶尔”足够少，足以冲淡缓慢的情况即可。摊销时间本质上是指“如果执行多次操作，则每次操作所花费的平均时间”。摊余时间不必是常数；你可以有线性和对数摊销时间或其他任何东西。
让我们以动态数组为例，您可以向其中重复添加新项目。通常添加一个项目需要常数时间（即 O(1)）。但每次数组已满时，您都会分配两倍的空间，将数据复制到新区域，并释放旧空间。假设分配和释放在恒定时间内运行，此扩大过程需要 O(n) 时间，其中 n 是数组的当前大小。
因此，每次放大所花费的时间大约是上次放大的两倍。但你在这样做之前也等待了两倍的时间！因此，每次扩展的成本可以在插入之间“分摊”。这意味着从长远来看，向数组添加 m 个项目所需的总时间为 O(m)，因此摊余时间（即每次插入的时间）为 O(1)。