Am Raum für den Auswahlalgorithmus gebunden?

Question

Es gibt einen bekannten schlechtesten Fall $ O (n) $ Auswahlalgorithmus Um das größte Element $ k $ 'in einer Reihe von ganzen Zahlen zu finden. Es verwendet a Median der Medianer Ansatz, um einen Pivot zu finden, verteilt sich das Eingangsarray und setzt dann rekursiv auf der Suche nach dem größten Element $ k $ fort.

Was wäre, wenn wir das Eingangsarray nicht berühren dürfen, wie viel zusätzlicher Platz benötigt, um das größte Element $ k $ 'in $ O (n) $ Zeit zu finden? Könnten wir das größte Element $ k $ 'th in $ O (1) $ zusätzlicher Platz finden und trotzdem die Laufzeit $ O (n) $ halten? Beispielsweise benötigt das Finden des maximalen oder minimalen Elements $ O (n) $ Zeit und $ O (1) $ Space.

Intuitiv kann ich mir nicht vorstellen, dass wir es besser machen könnten als $ O (n) $ Space, aber gibt es einen Beweis dafür?

Kann jemand auf eine Referenz hinweisen oder ein Argument entwickeln, warum das Element $ lfloor n/2 rfloor $ 'th $ o (n) $ Space in $ o (n) $ Zeit erfordern würde?

Answer 1

Es ist ein offenes Problem, wenn Sie mit $ O (n) $ Time und $ O (1) $ extra Speicherzellen ausgewählt werden können, ohne die Eingabe zu ändern (siehe hier). Aber du kannst dem ziemlich nahe kommen.

Munro und Raman schlugen eine vor Algorithmus zur Auswahl Das läuft in $ o (n^{1+ varepsilon}) $ Zeit, während nur $ o (1/ varepsilon) $ extra Storage (Zellen) verwendet wird. Dieser Algorithmus lässt den Eingang unverändert. Sie können alle kleinen $ varepsilon> 0 $ auswählen.

Im Kern wirkt der Algorithmus von Munro und Raman als klassischer $ o (n) $ algorithmus: Es unterhält a links und Rechts gebunden (genannt Filter), die zwei Elemente mit einem bekannten Rang sind. Das angeforderte Element liegt zwischen den beiden Filtern (Rangwise). Durch die Auswahl eines guten Pivot -Elements $ P $ können wir alle Nummern mit den Filtern und $ P $ überprüfen. Dies ermöglicht die Aktualisierung der Filter und verringert die Anzahl der zu prüfenden Elemente (ranglich). Wir wiederholen, bis wir das Anforderungselement gefunden haben.

Was sich vom klassischen Algorithmus unterscheidet, ist die Wahl von $ p $. Sei $ a (k) $ der Algorithmus, der die Auswahl für $ varepsilon = 1/k $ löst. Der Algorithmus $ a (k) $ teilt das Array in gleichgroße Blöcke und identifiziert einen Block, in dem sich viele Elemente befinden, deren Reihen zwischen den Filtern liegen (Existenz nach Taubenlochprinzip). Dieser Block wird dann mit Hilfe des Algorithmus $ A (K-1) $ nach einem guten Pivot-Element gescannt. Der Rekursionsanker ist der triviale $ a (1) $ -Algorithmus. Mit der richtigen Blockgröße (und der Mathematik) können Sie die oben angegebenen Laufzeit- und Platzanforderungen an die Anforderungen an die Zeit haben.

Übrigens wurden die Algorithmen, die Sie suchen, kürzlich benannt Algorithmen mit konstantem Raum.

Mir ist keine Untergrenze bekannt.