[解決済み] heapqライブラリの関数の時間複雑性は？

質問内容

質問なのですが、下記の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)

解決方法は？

heapq はバイナリヒープで、O(log n)である。 push とO(log n) pop . を参照してください。 heapq ソースコード .

あなたが示したアルゴリズムは、すべてのアイテムをヒープにプッシュするのにO(n log n)、そしてk番目の最大の要素を見つけるのにO((n-k) log n)を要します。つまり、複雑さは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)となります。