私の質問は、以下の 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)
ベストアンサー1
heapqpushはO(log n)とO(log n)のバイナリヒープですpop。heapq ソースコード。
あなたが示したアルゴリズムでは、すべての項目をヒープ上にプッシュするのに O(n log n) かかり、次に k 番目に大きい要素を見つけるのに O((nk) 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((nk) log n) です。つまり、O((nk) log n) になります。最悪の場合、O(n log n) になります。