Zufällige Auswahl

Der randomisierte Auswahlalgorithmus lautet wie folgt:

Eingabe: Ein Array aus (der Einfachheit halber eindeutigen) Zahlen und einer Zahl$A$$n$$k\in [n]$

Ausgabe: Das Element "Rang " von (dh das Element in Position wenn sortiert wurde)$k$$A$$k$$A$

Methode:

• Wenn es ein Element in , geben Sie es zurück$A$
• Wählen Sie ein Element (den "Pivot") gleichmäßig nach dem Zufallsprinzip aus$p$
• Berechnen Sie die Mengen und$L = \{a\in A : a < p\}$$R = \{a\in A : a > p\}$
• Wenn$|L| \ge k$ , gebe das Element Rang von L zurück .$k$$L$
• Andernfalls geben Sie den Rang Element von $k - |L|$$R$

Mir wurde folgende frage gestellt:

Nehmen wir an, dass , so dass Sie für den Median suchen und lassen & agr; & egr ; ( 1 / 2 , 1 ) eine Konstante. Wie groß ist die Wahrscheinlichkeit, dass die Menge mit dem Median beim ersten rekursiven Aufruf höchstens α n beträgt ?$k=n/2$$\alpha\in (1/2,1)$$\alpha n$

Mir wurde gesagt, dass die Antwort , mit der Begründung "Der ausgewählte Drehpunkt sollte zwischen 1 & agr; und & agr ; mal dem ursprünglichen Array liegen".$2\alpha - 1$$1−\alpha$$\alpha$

Warum? Als ist jedes Element, das als Drehpunkt gewählt wird, entweder größer oder kleiner als mehr als die Hälfte der ursprünglichen Elemente. Der Median liegt immer in der größeren Unteranordnung, da die Elemente in der unterteilten Unteranordnung immer kleiner als der Drehpunkt sind.$\alpha \in (0.5, 1)$

Wenn der Drehpunkt in der ersten Hälfte des ursprünglichen Arrays liegt (weniger als die Hälfte davon), befindet sich der Median mit Sicherheit in der zweiten größeren Hälfte, da er sich in der mittleren Position des Arrays befinden muss, sobald der Median gefunden wurde Alles vor dem Pivot ist kleiner als oben angegeben.

Wenn der Drehpunkt in der zweiten Hälfte des ursprünglichen Arrays liegt (mehr als die Hälfte der Elemente), wird der Median aus dem gleichen Grund sicherlich die erste größere Hälfte sein, bevor der Drehpunkt als kleiner betrachtet wird.

Beispiel:

3 4 5 8 7 9 2 1 6 10

Der Median ist 5.

Angenommen, der gewählte Drehpunkt ist 2. Nach der ersten Iteration lautet er also:

1 2 .... größerer Teil ....

Nur 1und 2werden nach der ersten Iteration getauscht. Nummer 5 (der Median) befindet sich noch in der ersten größeren Hälfte (entsprechend dem Drehpunkt 2). Der Punkt ist, dass der Median immer auf der größeren Hälfte liegt. Wie kann er eine Chance haben, in einem kleineren Subarray zu bleiben?

$n$$\alpha n$$(1-\alpha) n$$(1-\alpha) n$$\alpha > 1/2$$2 - 2\alpha$$1- 2 + 2\alpha=2\alpha - 1$