举一个简单的例子,在动态数组的特定实现中,每次填充时我们将数组的大小加倍.因此,可能需要重新分配阵列,并且在最坏的情况下,插入可能需要O(n).但是,n次插入的序列总是可以在O(n)时间内完成,因为其余的插入是在恒定时间内完成的,因此n次插入可以在O(n)时间内完成.因此,每次操作的摊销时间为O(n)/ n = O(1). - 来自维基
但在另一本书中:每次加倍需要O(n)时间,但很少发生,其摊销时间仍为O(1).
希望有人可以告诉我罕见的情况是否推断出Wiki的解释？谢谢
algorithm amortized-analysis
algorithm ×1
amortized-analysis ×1