使用heapq.heappop弹出所有元素所需的时间复杂性(Python3)

Question

现在，最初似乎应该是O(Nlog(N))，其中N是堆中的元素数，但在最坏的情况下，筛选每个元素需要花费log(N)时间，直到N/2节点被弹出(因为这意味着堆的高度减少了一个)，然后需要log(N)-1次对每个元素进行筛选，直到N/4个节点被弹出为止。

因此，它变成了一个系列

N/2*(log(N)) + N/4*(log(N)-1) + N/8*(log(N)-1) +N/(2^(log(N))*(log(N) -堆高)

最后一项基本上是N/N *0-0

我想不出这个系列的和，我试着用它的标准形式集成它。

N*(log(N) - x)/2^(x+1)dx的积分，以log(N)为限

但是wolfram给了我一个复杂的答案

Answer 1

如果堆中有n项，则弹出根项具有log(n)的最坏情况复杂性。然后堆上有n-1项，弹出根项的复杂性是log(n-1)。因此，您想要求和的序列是：

log(n) + log(n-1) + log(n-2) + log(n-3) + ... + log(n-n+1)

或者，更容易理解：

log(1) + log(2) + log(3) + ... + log(n)

https://stackoverflow.com/a/21152768/56778解释了如何是O(n log )以及Θ(n log )。

或者，log(a) + log(b)等于log(a*b)。因此，从1到n的日志之和等于log(n!)。请参阅https://math.stackexchange.com/questions/589027/whats-the-formula-to-solve-summation-of-logarithms

另见Is log(n!) = Θ(n·log(n))?