heapq库中的函数的时间复杂度是多少 [英] What's the time complexity of functions in heapq library

问题描述

我的问题来自下面的leetcode解决方案，我不明白为什么它是O(k+(n-k)log(k)).

My question is from the solution in leetcode below, I can't understand why it is O(k+(n-k)log(k)).

补充:也许不是那样的复杂性，实际上我不知道heappush()和heappop()

Supplement: Maybe the complexity isn't that, in fact I don't know the time complexity of heappush() and heappop()

# O(k+(n-k)lgk) time, min-heap
def findKthLargest(self, nums, k):
    heap = []
    for num in nums:
        heapq.heappush(heap, num)
    for _ in xrange(len(nums)-k):
        heapq.heappop(heap)
    return heapq.heappop(heap)

推荐答案

heapq是一个二进制堆，具有O(log n)push和O(log n)pop.请参见 heapq源代码.

heapq is a binary heap, with O(log n) push and O(log n) pop. See the heapq source code.

您显示的算法使用O(n log n)将所有项目推入堆，然后使用O((n-k)log n)查找第k个最大元素.因此，复杂度将为O(n log n).它还需要O(n)额外的空间.

The algorithm you show takes O(n log n) to push all the items onto the heap, and then O((n-k) log n) to find the kth largest element. So the complexity would be O(n log n). It also requires O(n) extra space.

您可以在O(n log k)中执行此操作，只需稍微修改算法即可使用O(k)多余的空间.我不是Python程序员，因此您必须翻译伪代码:

You can do this in O(n log k), using O(k) extra space by modifying the algorithm slightly. I'm not a Python programmer, so you'll have to translate the pseudocode:

# create a new min-heap
# push the first k nums onto the heap
for the rest of the nums:
    if num > heap.peek()
        heap.pop()
        heap.push(num)

# at this point, the k largest items are on the heap.
# The kth largest is the root:

return heap.pop()

此处的关键是，堆仅包含迄今为止看到的最大项目.如果一个项目小于到目前为止所见的第k个最大项目，则永远不会将其放入堆中.最坏的情况是O(n log k).

The key here is that the heap contains just the largest items seen so far. If an item is smaller than the kth largest seen so far, it's never put onto the heap. The worst case is O(n log k).

实际上，heapq有一个heapreplace方法，因此您可以替换为:

Actually, heapq has a heapreplace method, so you could replace this:

    if num > heap.peek()
        heap.pop()
        heap.push(num)

使用

    if num > heap.peek()
        heap.replace(num)

此外，推送第一个k项的替代方法是创建第一个k项的列表并调用heapify.一种更优化的算法(但仍然是O(n log k))是:

Also, an alternative to pushing the first k items is to create a list of the first k items and call heapify. A more optimized (but still O(n log k)) algorithm is:

# create array of first `k` items
heap = heapify(array)
for remaining nums
    if (num > heap.peek())
        heap.replace(num)
return heap.pop()

您还可以在整个数组上调用heapify，然后弹出第一个n-k项，然后取顶部:

You could also call heapify on the entire array, then pop the first n-k items, and then take the top:

heapify(nums)
for i = 0 to n-k
    heapq.heappop(nums)
return heapq.heappop(nums)

那更简单.不知道它是否比我以前的建议要快，但是会修改原始数组.复杂度是O(n)来构建堆，然后O((n-k)log n)用于弹出窗口.因此它是O((n-k)log n).最糟糕的情况是O(n log n).

That's simpler. Not sure if it's faster than my previous suggestion, but it modifies the original array. The complexity is O(n) to build the heap, then O((n-k) log n) for the pops. So it's be O((n-k) log n). Worst case O(n log n).

这篇关于heapq库中的函数的时间复杂度是多少的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！