algorithm - 3种不同情况下插入堆的时间复杂度

Question

我知道在将数字 1,2,3,......,n 插入到初始为空的最小堆中的情况下，顺序为 1,2,3 ,.......,n，你只需要将它们一一放入。但是我不太清楚如何计算两种不同情况的时间复杂度:如果以相反的顺序插入它们 (n,n-1,n-2,....,2,1) 甚至与顺序为 (1,n+1,2,n+2,3,n+3,....,n-1,2n-1,n,2n )。我知道对于相反的情况，您将不得不“沿着”堆的高度(即 logn)移动插入的数字，但我不太确定其余部分......

Answer 1

如您所说，当您按顺序将数字 0..n 插入到最小堆中时，每个项目的插入时间为 O(1)。因为您所要做的就是将数字追加到数组中。

当您以相反的顺序插入时，每个项目都被插入到底行，并且必须通过堆向上筛选到根。每次插入都必须向上移动 log(n) 行。所以每个项目的插入是 O(log n)。

平均值，当您随机插入项目时，如 Argument for O(1) average-case complexity of heap insertion 中详细讨论的那样以及它链接的文章，类似于 1.6。

因此有一个非常有力的论据，即二叉堆插入的平均复杂度是 O(1)。

在您的特定情况下，您的插入是交替的 O(1) 和 O(log n)。所以随着时间的推移，你有 O((1+log n)/2)，这将是 O(n log n) 来插入所有项目。