Finden Sie den Median des unsortierten Arrays in

Um den Median eines unsortierten Arrays zu finden, können wir einen Min-Heap in Zeit für Elemente erstellen und dann eins nach dem anderen Elemente extrahieren , um den Median zu erhalten. Dieser Ansatz würde jedoch Zeit in Anspruch nehmen . $O(n\log n)$ $n$ $n/2$ $O(n \log n)$

Können wir dasselbe mit einer Methode in Zeit machen? Wenn wir können, wie dann? $O(n)$

algorithms time-complexity Luv
quelle

en.wikipedia.org/wiki/Selection_algorithm

Jukka Suomela

@JukkaSuomela Warum nicht eine schnelle und einfache Antwort (im Idealfall mit einer kurzen Erläuterung eines solchen Algorithmus)?

Raphael

Beachten Sie die zugehörige Metadiskussion . Wie sich herausstellt, führen einfache Websuchen zur Beantwortung dieser Frage.

Raphael

stackoverflow.com/questions/2571358/median-of-a-billion-numbers

Evgeny

Antworten:

Dies ist ein Sonderfall eines Auswahlalgorithmus , der das kleinste Element eines Arrays finden kann, wobei die Hälfte der Größe des Arrays ist. Es gibt eine Implementierung, die im schlimmsten Fall linear ist. $k$ $k$

Generischer Auswahlalgorithmus

Schauen wir uns zuerst einen Algorithmus an find-kth, der das -kleinste Element eines Arrays findet: $k$

find-kth(A, k)
  pivot = random element of A
  (L, R) = split(A, pivot)
  if k = |L|+1, return pivot
  if k ≤ |L|  , return find-kth(L, k)
  if k > |L|+1, return find-kth(R, k-(|L|+1))

Die Funktion split(A, pivot)gibt L,Rso zurück, dass alle Elemente in Rgrößer sind als pivotund Lalle anderen (minus eines Vorkommens von pivot). Dann wird alles rekursiv gemacht.

Dies ist im Durchschnitt , aber im ungünstigsten Fall. $O(n)$ $O(n^2)$

Linearer Worst-Case: Der Median-of-Medians-Algorithmus

Ein besserer Pivot ist der Median aller Mediane von Subarrays der AGröße 5, indem die Prozedur für das Array dieser Mediane aufgerufen wird.

find-kth(A, k)
  B = [median(A[1], .., A[5]), median(A[6], .., A[10]), ..]
  pivot = find-kth(B, |B|/2)
  ...

Dies garantiert in allen Fällen . Es ist nicht so offensichtlich. Diese Powerpoint-Folien sind hilfreich, um sowohl den Algorithmus als auch die Komplexität zu erklären. $O(n)$

Beachten Sie, dass die meiste Zeit mit einem zufälligen Pivot schneller ist.

jmad
quelle

Ist diese Größe 5Standard? Was ist, wenn die Größe von A kleiner als 5 ist?

Jayesh

Für jedes feste n ist die Komplexität konstant, sofern sie nicht unendlich ist. Daher können Sie für diesen Sonderfall jeden gültigen Algorithmus mit endlicher Komplexität verwenden, auch wenn er O (2 ^ n) ist. Für ein festes n (dh höchstens 4 in jedem Fall) ist die Komplexität höchstens O (2 ^ 4) = O (1).

v6ak

Beim ersten Algorithmus: return A[k]ist falsch (es Asei denn, es ist sortiert, was den Algorithmus zur Diskussion bringen würde). Wenn es splitpassiert ist, teilen Sie sich Aso, dass k = |L| + 1Sie immer noch nicht wissen, wo sich das kth-Element befindet. Ihr Grundfall ist, wenn |A| = 1Sie noch einen der beiden rekursiven Aufrufe durchführen müssen.

wcochran

@ NickCaplinger repariert mit web.archive.org

jmad

Ist das nicht der schlimmste Fall für den generischen Auswahlalgorithmus O (NlogN)? Auch wenn die rekursiven Aufruf Blätter nur 10% des Arrays nach jedem Anruf, dann ist es immer noch ein Logarithmus in Basis 10

octavian

$n^{-1/4}$ $O(n)$

Die Hauptidee des Algorithmus ist die Verwendung von Stichproben. Wir müssen zwei Elemente finden, die in der sortierten Reihenfolge des Arrays nahe beieinander liegen und zwischen denen der Median liegt. Eine vollständige Beschreibung finden Sie in der Referenz [MU2017].

[MU2017] Michael Mitzenmacher und Eli Upfal. "Wahrscheinlichkeit und Berechnung: Randomisierung und probabilistische Techniken in Algorithmen und Datenanalyse", Kapitel 3, Seiten 57-62. Cambridge University Press, Zweite Ausgabe, 2017.

zdm
quelle