在这个结构中插入一个元素的摊余时间复杂性是多少

Question

假设您使用数组实现了一个堆，每次数组满时，您都会将其复制到一个大小是其两倍的数组中。将元素插入堆的摊余时间复杂度(在最坏的情况下)是多少？

我认为我们有T(n) = n * n(在最坏的情况下，这是一个n个运算序列的总成本的上界)，然后根据一个公式摊销的复杂度是T(n) / n = n^n / n = n。

但我认为这是非常错误的，因为直觉很清楚我应该得到log(n)或更低。。。那么我该如何计算呢？

Answer 1

想象一下，将n个元素插入以这种方式表示的堆中。有两种不同的成本来源需要考虑：

1. 堆操作的成本，忽略底层数组的大小
2. 数组的成本会调整大小，忽略总体堆操作

在总共n个操作中，(1)的开销为O(n log n)，因为每次堆插入都需要时间O(log n)。

对于(2)的成本，请注意，使数组大小加倍所做的工作与数组加倍时的大小成正比。这意味着你要做1个单位的工作来将数组从大小1加倍，2个单位的工作量来将数组大小2加倍，4个单位的工时来将数组尺寸4加倍，等等。这意味着完成的总工作量是

1+2+4+8+16+…+2^{1+log n}≤4n-1=O(n)

此数学使用的事实是，在数组达到大小n之前，最多只将数组加倍1+logn次，并且1+2+4+8+…+2^k=2^k+1-1。这意味着，在所有n个插入中，您要做O(n)工作，使数组加倍。

总体而言，n次操作完成的总工作量为O(n-logn)，因此每次操作的摊余成本为O(logn)。