Meine Frage ist von der Lösung in leetcode unten, ich kann nicht verstehen, warum es O(k+(n-k)log(k)) ist.
Nachtrag: Vielleicht ist die Komplexität nicht so groß, tatsächlich kenne ich die zeitliche Komplexität von heappush() und heappop()
heapq ist ein binärer Heap mit O (log n) push und O (log n) pop . Sehen Sie sich den heapq-Quellcode an.
Der von Ihnen angezeigte Algorithmus nimmt O (n log n), um alle Elemente auf den Heap zu schieben, und dann O ((n-k) log n), um das k-te größte Element zu finden. Also wäre die Komplexität O (n log n). Es erfordert auch O (n) zusätzlichen Speicherplatz.
Sie können dies in O (n log k) tun, indem Sie O (k) extra space verwenden, indem Sie den Algorithmus etwas modifizieren. Ich bin kein Python-Programmierer, also müssen Sie den Pseudocode übersetzen:
%Vor%Der Schlüssel hier ist, dass der Haufen nur die größten bisher gesehenen Elemente enthält. Wenn ein Gegenstand kleiner als der bisher größte k ist, wird er nie auf den Haufen gelegt. Der schlimmste Fall ist O (n log k).
Tatsächlich hat heapq eine heapreplace Methode, also könntest du das ersetzen:
mit
%Vor% Eine Alternative zum Verschieben der ersten k -Objekte besteht auch darin, eine Liste der ersten k -Elemente zu erstellen und heapify aufzurufen. Ein optimierter (aber immer noch O (n log k)) Algorithmus ist:
Sie könnten auch heapify für das gesamte Array aufrufen, dann die ersten n-k -Objekte aufrufen und dann die oberste:
Das ist einfacher. Ich bin mir nicht sicher, ob es schneller ist als mein vorheriger Vorschlag, aber es verändert das ursprüngliche Array. Die Komplexität ist O (n), um den Heap aufzubauen, und dann O ((n - k) log n) für die Pops. Also ist es O ((n-k) log n). Worst Case O (n log n).