將元素插入此結構的分期時間複雜度是多少？

Question

假設您使用數組實現一個堆，並且每次數組滿了時，都將其複製到一個數組的兩倍大小。將元素插入堆的分期時間複雜性（最差情況）是什麼？

我認爲我們有T(n) = n * n（這是最壞情況下n個操作序列的總成本的上限），然後根據一個公式的攤銷複雜度爲T(n)/n = n^n/n = n。

但我認爲這是非常錯誤的，因爲從直覺上我很清楚我應該得到log(n)或更低......所以我應該如何計算這個？

Answer 1

想象一下，您將n個元素插入到以這種方式表示的堆中。有兩種不同的成本來源需要考慮：

1. 堆操作的成本，忽略底層數組的大小。
2. 數組大小的成本調整大小，忽略整體堆操作。

因爲每個堆的插入花費時間O（log n），所以總共n次操作中（1）的代價爲O（n log n）。

對於（2）的代價，請注意，將數組的大小加倍的工作與數組大小成倍增加時的大小成正比。這意味着你需要完成1個工作單元來將數組從2號加倍，2個工作單元將數組從2號加倍，4個工作單元將數組從4號加倍，等等。這意味着總數完成的工作是

1 + 2 + 4 + 8 + 16 + ... + 2 ^{1 +日誌N} ≤ 4N - 1 = O（N）

此數學使用的事實在n達到n值之前，你最多隻能將陣列加倍1 + log n，並且1 + 2 + 4 + 8 + ... + 2 ^k = 2 ^{k + 1} - 1.這意味着在所有n次插入中，你做O（n）的工作倍增數組。總的來說，在n個操作中完成的總工作是O（n log n），因此每次操作的攤銷成本爲O（log n）。