python - heapq 库中函数的时间复杂度是多少

Question

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

补充:可能复杂度不是这个，其实我不知道heappush()和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)

Answer 1

heapq 是一个二进制堆，具有 O(log n) push 和 O(log n) pop。见 heapq source code .

你展示的算法需要 O(n log n) 将所有项目推送到堆上，然后 O((n-k) log n) 找到第 k 个最大元素。所以复杂度是 O(n log n)。它还需要 O(n) 额外空间。

您可以在 O(n log k) 中执行此操作，通过稍微修改算法使用 O(k) 额外空间。我不是 Python 程序员，所以你必须翻译伪代码:

# 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)。

其实 heapq 有一个 heapreplace 方法，所以你可以替换这个:

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

与

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

此外，推送前 k 项的替代方法是创建前 k 项的列表并调用 heapify。更优化(但仍为 O(n log k))的算法是:

# 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个元素，然后取顶部:

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)。