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源代码.

您显示的算法需要O(n log n)将所有项目推送到堆上,然后使用O((nk)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((nk)log n)为pops.所以它是O((nk)log n).最坏情况O(n log n).

Answer 2

heapify() 实际上需要线性时间，因为该方法与调用 heapq.push() N 次不同。

heapq.push()/heapq.pop() 需要 log n 时间，因为它会调整给定高度/级别的所有节点。

当您在 heapify() 中传递数组时，它会确保该节点的左右子节点已经维护了堆属性，无论它是最小堆还是最大堆。

你可以看这个视频： https://www.youtube.com/watch ?v=HqPJF2L5h9U

https://www.youtube.com/watch?v=B7hVxCmfPtM

希望这会有所帮助。

Answer 3

从@Shivam purbia 的帖子总结：

1. 使用heaps.heapify()可以降低时间和空间复杂度，因为它heaps.heapify()是就地堆化并且运行它的成本是线性的。
2. 两者heapq.heappush()都heapq.heappop()花费O(logN)时间复杂度

最终代码将是这样的......

import heapq

def findKthLargest(self, nums, k):
    heapq.heapify(nums)            # in-place heapify -> cost O(N) time
    
    for _ in range(len(nums)-k):   # run (N-k) times
        heapq.heappop(heap)        # cost O(logN) time
    return heapq.heappop(heap)     

• 总时间复杂度为O((N - k)logN)
• 总空间复杂度为O(1)