一个时间复杂度为O(1)的摊还操作是否可能在最坏情况下需要O(n^2)的时间？

Question

如果一个操作的平摊时间为O(1)，它是否可能在最坏情况下需要O(N^2)的时间？

- bst-for-life

Answer 1

是的，可以。摊销复杂度考虑了最坏情况出现的频率。因此，只要最坏情况在大约1个N²次操作中出现一次，摊销复杂度就会是常数。

我们来举个简单的例子——动态扩展数组（我将其称为vector，因为在大多数语言中都是这样称呼）。在大多数情况下，向后推一个元素的时间是恒定的。大多数情况下，推送元素是一个简单的赋值操作，但偶尔会分配所有分配的元素，我们需要重新分配vector。这将是push_back操作的最坏情况，当发生这种情况时，操作的时间复杂度是线性的。但是，vector增长的方式确保重新分配的频率不太频繁。每次vector重新分配时，它的大小都会加倍。因此，在另一次重新分配之前，我们将进行n个简单的push_back操作（假设n是重新分配之前的vector容量）。因此，线性复杂度的最坏情况最多出现一次。

类似于上面的情况，想象一种数据结构，在O(n²)内重新分配，但确保重新分配在n²个常数操作内最多执行一次。这将是具有摊销复杂度O(1)和最坏情况复杂度O(N²)的操作的示例。

- Ivaylo Strandjev