K größten Elemente eines Arrays, Sortieralgorithmus

Question

Ich habe auf dieses Problem fest und hoffte, jemand würde die Antworten geben und erklären Sie bitte.

Sie erhalten ein unsortiertes Array A von Ints mit nicht wiederholten Elementen und werden gebeten, die Kth größten Elemente in absteigender sortierter Reihenfolge zu finden. Wenn zum Beispiel A das Array [11,6,1,2,15,7,4,8,20] und K = 3 ist, dann sollte die Antwort [20,15,11] lauten. Beschreiben Sie, wie Sie die Sortierreihenfolge und Heapsort ändern würden, um dieses Problem zu lösen (zwei separate Antworten). Was ist die Worst-Case-Laufzeit Ihrer Algorithmen, als eine Funktion von N = A.Länge und K?

Answer 1

Welche Auswahl Art normalerweise der Fall ist:

• höchste Element finden, swap auf den ersten Platz
• nächsthöhere Element, swap auf den zweiten Platz finden
• ...
• finden Second-to- letztes Element, Wechsel auf vorletzten Platz
• Fertig.

ist die normale Laufzeit O(N * N), da jeder der N Schritte ein Suchproblem ist, die O(N) ist.

Sie können einfach aufhören, wenn Sie die ersten K-Elemente gefunden haben. Wenn Sie es früh abbrechen, ist es nicht mehr N Schritte; aber jeder Schritt ist unverändert.

und so der Big-O

der abgebrochenen Auswahl Art ist somit O(K * N).

Die Heap-Sortierung erfolgt in zwei Schritten: Heapify und Siftdown. Heapify (Erstellen der Heap-Struktur) muss ordnungsgemäß durchgeführt werden und bleibt unverändert. Da es in weniger Operationen als in der Sichtung durchgeführt wird, wird es in der großen Sortierung nicht berücksichtigt.

Siftdown (Elemente aus dem Heap in ein sortiertes Array swapping) ist sehr, sehr ähnlich Auswahl sortieren, aber die Operation in jeder von N Schritten der nächsthöchsten Element zu finden ist schneller: O(log N).

Da siftdown so ziemlich das Gleiche tut, konzeptionell, wie die Auswahl sortieren, können Sie das auch so schnell abbrechen, da sie die besten Ergebnisse K gefunden hat.

Dies bedeutet, dass die Big-O

des abgebrochenen Stapelsortier ist somit O(K * log N).