Was ist der schnellste Weg, um den K-ten kleinsten Wert in einer unsortierten Liste ohne Sortierung zu finden?

8

Mein anfänglicher Algorithmus:

  1. Vergleichen Sie Element 0 mit jedem anderen Element und verfolgen Sie, wie viele Elemente kleiner sind.
  2. Wiederholen Sie diesen Vorgang für jedes Element, bis ein Element gefunden wird, das größer als genau (k-1) Elemente ist.

Ich gehe davon aus, dass dies im schlimmsten Fall dauern würde . Kann eine schnellere Laufzeit erreicht werden, ohne die Liste zu sortieren?Ö(n2)

search-algorithms lists WARUM
quelle
9
Mögliches Duplikat des Findens
user2357112 unterstützt Monica
Können Sie eine zweite Liste erstellen und sortieren? Dh Können Sie eine Liste der k kleinsten Werte erstellen?
jmoreno

Antworten:

10

Verwenden Sie den Auswahlalgorithmus für die lineare Zeit https://en.m.wikipedia.org/wiki/Selection_algorithm

Eugene
quelle
2
Insbesondere Median of Medians von Blum et al., 1973, löst das Auswahlproblem in der linearen Zeit im ungünstigsten Fall. Wahrscheinlich der eleganteste Algorithmus, den ich je gesehen habe.
Quicksort
6
Obwohl dies die Frage beantwortet, wird empfohlen, eine eigene Beschreibung zu erstellen, nicht nur einen Link.
Evil
4

Leider kann ich nicht nur einen Kommentar abgeben, sondern muss ihn als Antwort posten.

Wie auch immer, Sie könnten versuchen, einen Min-Heap für Ihr unsortiertes Array zu verwenden. Sie sollten in der Lage sein, eine Zeitkomplexität von O (n + k * logn) zu erhalten.

Luca Giorgi
quelle
3
Leider kann ich nicht nur einen Kommentar abgeben, sondern muss ihn als Antwort posten. - was gut war, da Antworten wie Ihr Beitrag nicht in die Kommentare gehören. Kommentare dienen der Verbesserung der Fragen, nicht kurzen Antworten oder Ähnlichem.
Wrzlprmft
1
Mh, ich habe das Gefühl, dass meine Antwort keine vollständige Antwort ist, um ehrlich zu sein. Ich habe keine genauen Angaben darüber gemacht, warum oder wie die Verwendung eines Min-Heaps die zeitliche Komplexität verringern könnte. Deshalb fühlte ich mich dazugehörig mehr in einem Kommentar als in einer Antwort
Luca Giorgi
Es hängt von ob Min-Heap oder Max-Heap verwendet werden soll. k
Evil
3

Der Quickselect-Algorithmus kann dies bei einer durchschnittlichen Komplexität von O (n) tun. Er ist laut Wikipedia einer der am häufigsten verwendeten Auswahlalgorithmen .

Es ist von QuickSort abgeleitet und leidet als solches unter einer O (n²) Worst-Case-Komplexität, wenn Sie einen schlechten Pivot verwenden (ein Problem, das in der Praxis vermieden werden kann).

Der Algorithmus auf den Punkt gebracht: Steigen Sie nach dem Schwenken wie in QuickSort nur in die untere oder obere Seite des Arrays ab - je nachdem, welches von ihnen das gewünschte Element enthält.

Nestor Demeure
quelle
2

kk

  1. k
  2. ich
    • M.
    • ich<M.M.ich

k

Ö(k)Ö(n.Log⁡k)

Behrouz Babaki
quelle
1
Max-Heap oder Min-Heap, es hängt von k> n / 2 ab.
Evil
@ Evil Sie möchten überprüfen, ob i kleiner als eines der Elemente im Heap ist. Sie möchten also wissen, ob es kleiner als das größte von ihnen ist. Nachschlagen des maximalen Elements ist O (1) in max-heap, aber nicht in min-heap.
Behrouz Babaki
1
Wahr. Stellen Sie sich vor, k = 1 oder k = n, würden Sie in beiden Fällen denselben Heap verwenden? Vielleicht ist es möglich, den Min-Heap irgendwie zu benutzen, wenn er schneller ist? (Ich weiß es ist, du hast +1 von mir, nur ein Trottel, mach dir keine Sorgen).
Evil
1
@ Evil Du hast recht. Ich habe Ihren Kommentar hastig verworfen. Wenn k> n / 2 ist, kann man eine ähnliche Methode verwenden, um die (nk) größten Elemente in einem Min-Heap zu speichern. Die vom Heap entfernten Elemente sind das, was wir wollen.
Behrouz Babaki