algorithm - 3种不同情况下插入堆的时间复杂度
问题描述
我知道，在将数字插入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），但我不太确定其余部分......
解决方案
正如您所说，当您将数字 0..n 按顺序插入最小堆时，每个项目的插入时间为 O(1)。因为您所要做的就是将数字附加到数组中。
当您以相反的顺序插入时，每个项目都插入到底行，并且必须通过堆向上筛选到根。每次插入都必须向上移动 log(n) 行。所以每个项目的插入是 O(log n)。
当您随机插入项目时，如在堆插入的 O(1) 平均情况复杂度及其链接的文章的参数中详细讨论过的，平均值约为1.6。
所以有一个非常强烈的论点是二进制堆插入的平均复杂度是 O(1)。
在您的特定情况下，您的插入是交替的 O(1) 和 O(log n)。所以随着时间的推移，你有 O((1+log n)/2)，这将是 O(n log n) 来插入所有的项目。