complexity-theory - 花费 O(1) 摊销时间的操作可以有最坏情况 O(n^2) 时间吗？

Question

如果一个操作的摊销时间为 O(1)，那么在最坏的情况下，它可以花费 O(N^2) 时间吗？

Answer 1

Yes, it can. Amortized complexity takes into account the frequency with which the worst case appears. Thus as soon as the worst case appears in about 1 in N^2 operations the amortized complexity will be constant.

Let's take a simple example - the dynamically expanding array(I will call that vector as it is called in c++) in most languages has an amortized constant time for pushing an element to its back. Most of the time pushing an element is a simple assignment of a value, but once in a while all the elements allocated will be assigned and we need to re-allocate the vector. This would be the worst case of a push_back operation and when that happens the operation is with linear complexity. Still the way vector grows makes sure that re-allocation is infrequent enough. Each time the vector is re-allocated it doubles its size. Thus before another re-allocation happens we will have n simple push_back operations(assuming n was the capacity of the vector before re-allocation). As a result the worst case of linear complexity appears at most once in a linear number of operations.

Analogously to the case above imagine a data structure that re-allocates in O(n^2), but makes sure that re-allocation is performed at most once in n^2 constant operations. This would be an example of an operation with amortized complexity of O(1) and worst-case complexity O(N^2).