假设您使用数组实现堆，并且每次数组已满，您将其复制到其大小的两倍的数组 . 将元素插入堆中的摊销时间复杂度（最坏的情况）是多少？
我认为我们有 T(n) = n * n （这是最坏情况下n个操作序列的总成本的上限），然后根据一个公式的摊销复杂度是 T(n) / n = n^n / n = n .
T(n) = n * n
T(n) / n = n^n / n = n
但我认为这是非常错误的，因为从直觉上可以清楚地知道我应该得到 log(n) 或更低......所以我应该如何计算呢？
log(n)
想象一下，您将n个元素插入到以这种方式表示的堆中 . 您需要考虑两种不同的成本来源：
堆操作的成本，忽略基础数组的大小 .
数组的成本调整大小，忽略了总体堆操作 .
（1）的成本在n个总操作中是O（n log n），因为每个堆插入需要时间O（log n） .
对于（2）的成本，请注意，将数组大小加倍的工作与数组加倍时的大小成正比 . 这意味着你将完成1个单位的工作，将数组从1号大小加倍，2个单位的工作量从2号大小加倍，4个单位的工作量从4号大小加倍，等等 . 这意味着总数完成的工作是
1 2 4 8 16 ... 21 logn≤4n - 1 = O（n）
这个数学运算使用的事实是，在最大大小为n之前，你只能将数组加倍最多1 log n次，并且1 2 4 8 ... 2k = 2k 1 - 1.这意味着在所有n次插入中你做O （n）将阵列加倍 .
总体而言，在n个操作中完成的总工作量为O（n log n），因此每个操作的摊销成本为O（log n） .
1 回答
想象一下，您将n个元素插入到以这种方式表示的堆中 . 您需要考虑两种不同的成本来源：
堆操作的成本，忽略基础数组的大小 .
数组的成本调整大小，忽略了总体堆操作 .
（1）的成本在n个总操作中是O（n log n），因为每个堆插入需要时间O（log n） .
对于（2）的成本，请注意，将数组大小加倍的工作与数组加倍时的大小成正比 . 这意味着你将完成1个单位的工作，将数组从1号大小加倍，2个单位的工作量从2号大小加倍，4个单位的工作量从4号大小加倍，等等 . 这意味着总数完成的工作是
这个数学运算使用的事实是，在最大大小为n之前，你只能将数组加倍最多1 log n次，并且1 2 4 8 ... 2k = 2k 1 - 1.这意味着在所有n次插入中你做O （n）将阵列加倍 .
总体而言，在n个操作中完成的总工作量为O（n log n），因此每个操作的摊销成本为O（log n） .