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（n個のログ）pushとOで、バイナリヒープあるかわからない、それではありません（logn）pop。 heapq source codeを参照してください。

あなたが表示するアルゴリズムは、すべての項目をヒープにプッシュするために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個のkをログ））のアルゴリズムは、次のとおりです。

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

あなたはまた、最初n-kアイテムをポップ、その後、配列全体にheapifyを呼び出し、その後トップを取ることができる：

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