使用 heapq.heappop 弹出所有元素所需的时间复杂度 (Python 3)
Time complexity required to pop all elements using heapq.heappop (Python 3)
现在最初看起来应该是 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) - Height of Heap)
最后一项基本上是 N/N * 0 - 0
我无法算出这个级数的总和，我尝试将其积分为标准形式
N*(log(N) - x)/2^(x+1)dx 的积分，将 0 限制为 log(N)
但 wolfram 给了我一个复杂的答案
如果堆中有 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)
解释了 O(n log n) 以及 Θ(n log n) 的原理。
或者，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))?
现在最初看起来应该是 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) - Height of Heap)
最后一项基本上是 N/N * 0 - 0
我无法算出这个级数的总和，我尝试将其积分为标准形式
N*(log(N) - x)/2^(x+1)dx 的积分，将 0 限制为 log(N)
但 wolfram 给了我一个复杂的答案
如果堆中有 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)
解释了 O(n log n) 以及 Θ(n log n) 的原理。
或者，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))?