Scharfe Konzentration für die Selektion durch zufällige Partitionierung?

Question

Der übliche einfache Algorithmus für das Finden des Medianelements in einem Array $ A $ von $ n $ Zahlen lautet:

• Beispiel $ n^{3/4} $ Elemente von $ a $ mit Ersatz in $ b $
• Sortieren Sie $ b $ und finden Sie den Rang $ | b | pm sqrt {n} $ Elements $ l $ und $ r $ von $ b $
• Überprüfen Sie, ob $ L $ und $ R $ auf gegenüberliegenden Seiten des Median von $ a $ liegen und dass es höchstens $ c sqrt {n} $ Element konstant $ c> 0 $. Scheitern, wenn dies nicht passiert.
• Ansonsten finden Sie den Median, indem Sie die Elemente von $ a $ zwischen l $ und $ R $ sortieren

Es ist nicht schwer zu erkennen, dass dies in der linearen Zeit läuft und dass es mit hoher Wahrscheinlichkeit erfolgreich ist. (Alle schlechten Ereignisse sind große Abweichungen von der Erwartung eines Binomials entfernt.)

Ein alternativer Algorithmus für das gleiche Problem, das Schülern, die schnell gesehen haben, natürlicher ist, ist die hier beschriebene: Randomisierte Auswahl

Es ist auch leicht zu erkennen, dass dieser eine lineare erwartete Laufzeit hat: Sagen Sie, dass eine "Runde" eine Abfolge rekursiver Anrufe ist, die endet, wenn man einen 1/4-3/4-Split angibt, und dann beobachten, dass die erwartete Länge von Eine Runde ist höchstens 2. (im ersten Unentschieden einer Runde ist die Wahrscheinlichkeit, eine gute Spaltung zu erhalten, 1/2 und dann nach tatsächlich erhöht, da der Algorithmus so beschrieben wurde, dass die runde Länge von einer geometrischen Zufallsvariablen dominiert wird.)

Also jetzt die Frage:

Ist es möglich zu zeigen, dass die randomisierte Selektion in der linearen Zeit mit hoher Wahrscheinlichkeit läuft?

Wir haben $ o ( log n) $ Runden, und jede Runde hat eine Länge von mindestens $ k $ mit Wahrscheinlichkeit höchstens $ 2^{-k+1} $ log log n) $ mit Wahrscheinlichkeit $ 1-1/o ( log n) $.

Das ist etwas unbefriedigend, aber ist es eigentlich die Wahrheit?

Answer 1

Es ist nicht wahr, dass der Algorithmus in linearer Zeit mit hoher Wahrscheinlichkeit läuft. In Anbetracht der ersten Runde beträgt die Laufzeit mindestens $ theta (n) $ -mal a $ g (1/2) $ Random Variable. Sei $ p (n) longrightarrow 0 $ die zulässige Ausfallwahrscheinlichkeit. Da $ pr [g (1/2) Geq log_2 p (n)^{-1}] = p (n) $, beträgt die Laufzeit mindestens $ Omega (N log_2 p (n)^ {-1}) = Omega (n) $.

(Es gibt einige Betrugsfälle, da die Länge der ersten Runde nicht wirklich $ G (1/2) $ ist. Eine sorgfältige Analyse kann diese Antwort möglicherweise bestätigen oder nicht.)

EDIT: Grubel und Rosler haben bewiesen, dass die erwartete Anzahl von Vergleiche geteilt durch $ n $ (in gewissem Sinne) zu einer gewissen Grenzverteilung, die unbegrenzt ist, tendiert. Siehe zum Beispiel Grubels Papier "Hoare's Auswahlalgorithmus: Ein Markov -Kettenansatz", der auf ihr ursprüngliches Papier verweist.