Randomisierte Auswahl

Question

Der randomisierte Selektionsalgorithmus lautet wie folgt:

Eingabe: Ein Array $ A $ $ n $ (verschieden, für Einfachheit) und eine Zahl $ k in [n] $

Ausgabe: Das "Rang $ k $ Element" von $ a $ (dh der in Position $ k $, wenn $ a $ sortiert wurde)

Methode:

• Wenn es ein Element in $ a $ gibt, geben Sie es zurück
• Wählen Sie ein Element $ p $ ("Pivot") gleichmäßig zufällig
• Berechnen Sie die Sets $ l = {a in a: a <p } $ und $ r = {a in a: a> p } $
• Wenn $ | l | ge k $, zurück den Rang $ k $ Element von $ l $.
• Andernfalls geben Sie den Rang $ k - | l | $ Element von $ r $ zurück

Mir wurde die folgende Frage gestellt:

Nehmen wir an, dass Sie also nach dem Median suchen und $ alpha in (1/2,1) $ eine Konstante sein. Wie hoch ist die Wahrscheinlichkeit, dass bei dem ersten rekursiven Anruf der Set, der den Median enthält, höchstens $ alpha n $ hat?

Mir wurde gesagt, dass die Antwort $ 2 Alpha - 1 $ beträgt, wobei die Begründung "Der ausgewählte Drehpunkt sollte zwischen 1 $ Alpha $ und $ alpha $ -mal das ursprüngliche Array liegen".

Wieso den? Wie $ alpha in (0,5, 1) $, welches Element, das als Drehpunkt ausgewählt wird, ist entweder größer oder kleiner als mehr als die Hälfte der ursprünglichen Elemente. Der Median liegt immer in der größeren Subtarray, weil die Elemente in der partitionierten Subtarray immer geringer sind als der Drehpunkt.

Wenn der Drehpunkt in der ersten Hälfte des ursprünglichen Arrays (weniger als die Hälfte von ihnen) liegt, wird der Median sicherlich in der zweiten größeren Hälfte sein, denn sobald der Median gefunden wird, muss er sich in der mittleren Position des Arrays befinden, und Alles vor dem Drehpunkt ist kleiner, wie oben angegeben.

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

Beispiel:

3 4 5 8 7 9 2 1 6 10

Der Median ist 5.

Angenommen, der gewählte Drehpunkt beträgt 2. Nach der ersten Iteration wird es also:

1 2 .... Größerer Teil ....

Nur 1 und 2 werden nach der ersten Iteration ausgetauscht. Nummer 5 (der Median) befindet sich noch in der ersten größeren Hälfte (abgehoben auf den Drehpunkt 2). Der Punkt ist, dass der Median immer auf einer größeren Hälfte liegt, wie kann es die Chance haben, in einer kleineren Subtarray zu bleiben?

Answer 1

Angenommen, Ihr Array hat $ n $ Elemente. Wie Sie bemerkt haben, ist der Median nach der ersten Aufteilung immer im größeren Teil. Der größere Teil hat höchstens $ alpha n $, wenn der kleinere Teil mindestens $ (1- alpha) n $ hat. Dies geschieht, wenn Sie einen Drehpunkt auswählen, der nicht zu den kleinsten oder größten $ (1- alpha) n $ Elements ist. Weil $ alpha> 1/2 $, wissen Sie, dass dies disjunkte Sätze sind, daher beträgt die Wahrscheinlichkeit, eine der schlechten Drehungen zu treffen $.