向该结构中插入元素的摊销时间复杂度是多少? [英] What is the amortized time complexity of inserting an element to this structure?

问题描述

假设您使用数组实现堆，并且每次数组已满时，您将其复制到一个两倍大小的数组中.将元素插入堆的分摊时间复杂度(最坏情况)是多少?

Assume you implement a heap using an array and each time the array is full, you copy it to an array double its size. What is the amortized time complexity (for the worst case) of inserting elements into the heap?

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

I think that we have T(n) = n * n (which is an upper bound on the total cost of a sequence of n operations in the worst case), and then the amortized complexity according to one formula is T(n) / n = n^n / n = n.

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

But I think it is very wrong because it is very clear from intuition that I should get log(n) or lower ... So how should I calculate this?

推荐答案

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

Imagine that you insert n elements into a heap represented this way. There are two different sources of costs you need to factor in:

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

(1) 的成本在 n 次总操作中是 O(n log n)，因为每次堆插入需要 O(log n) 时间.

The cost of (1) is O(n log n) across n total operations, since each heap insertion takes time O(log n).

对于 (2) 的成本，请注意将数组大小加倍所做的工作与数组加倍时的大小成正比.这意味着您将做 1 个工作单元将数组从大小 1 加倍，2 个工作单元将数组从大小 2 加倍，4 个工作单元将数组从大小 4 加倍，等等.这意味着总完成的工作是

For the cost of (2), notice that the work done to double the size of the array is directly proportional to the size of the array at the time that it's doubled. This means that you'll do 1 unit of work to double the array from size 1, 2 units of work to double the array from size 2, 4 units of work to double the array from size 4, etc. This means that the total work done is

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

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

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

This math uses the fact that you only double the array at most 1 + log n times before it gets up to size n and that 1 + 2 + 4 + 8 + ... + 2^k = 2^k+1 - 1. This means that across all n insertions you do O(n) work doubling the array.

总的来说，n 个操作完成的总工作是 O(n log n)，所以每个操作的摊销成本是 O(log n).

Overall, the total work done across n operations is O(n log n), so the amortized cost per operation is O(log n).

这篇关于向该结构中插入元素的摊销时间复杂度是多少?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！