Platz für Auswahlalgorithmus gebunden?

Es gibt einen bekannten -Auswahlalgorithmus im ungünstigsten Fall , um das k -te größte Element in einem Array von ganzen Zahlen zu finden. Es verwendet einen Median-of-Medians- Ansatz, um einen ausreichend guten Pivot zu finden, partitioniert das Eingabearray an Ort und Stelle und setzt dann die Suche nach dem k -ten größten Element rekursiv fort .$O(n)$ $k$$k$

Was wäre, wenn wir das Eingabearray nicht berühren könnten, wie viel zusätzlicher Speicherplatz würde benötigt, um das -te größte Element in O ( n ) -Zeit zu finden? Könnten wir das k -te größte Element in O ( 1 ) zusätzlichen Raum finden und trotzdem die Laufzeit O ( n ) behalten ? Zum Beispiel benötigt das Finden des maximalen oder minimalen Elements O ( n ) Zeit und O ( 1 ) Raum. $k$$O(n)$$k$$O(1)$$O(n)$$O(n)$$O(1)$

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

Kann jemand auf eine Referenz verweisen oder ein Argument warum das ⌊ n / 2 ⌋ -te Element erfordern würde, dass O ( n ) -Raum in O ( n ) -Zeit gefunden wird?$\lfloor n/2 \rfloor$$O(n)$$O(n)$

Es ist ein offenes Problem, wenn Sie die Auswahl mit Zeit und O ( 1 ) zusätzlichen Speicherzellen durchführen können, ohne die Eingabe zu ändern (siehe hier ). Aber Sie können dem ziemlich nahe kommen.$O(n)$$O(1)$

Munro und Raman schlugen einen Algorithmus zur Auswahl vor , der in -Zeit ausgeführt wird, während nur O ( 1 / ε ) zusätzlicher Speicher (Zellen) verwendet wird. Dieser Algorithmus lässt die Eingabe unverändert. Sie können jedes kleine ε > 0 auswählen .$O(n^{1+\varepsilon})$$O(1/\varepsilon)$$\varepsilon>0$

Der Algorithmus von Munro und Raman funktioniert im Kern wie der klassische -Algorithmus: Er behält eine linke und eine rechte Grenze ( Filter genannt ) bei, die zwei Elemente mit bekanntem Rang sind. Das angeforderte Element befindet sich zwischen den beiden Filtern (nach Rang). Durch Auswahl eines guten Schwenkelements p können wir alle Zahlen mit den Filtern und p vergleichen . Dies ermöglicht die Aktualisierung der Filter und verringert die Anzahl der zu überprüfenden Elemente (nach Rang). Wir wiederholen, bis wir das Anfrageelement gefunden haben.$O(n)$$p$$p$

Was sich vom klassischen Algorithmus unterscheidet, ist die Wahl von . Sei A ( k ) der Algorithmus, der die Auswahl für ε = 1 / k löst . Der Algorithmus A ( k ) unterteilt das Array in gleich große Blöcke und identifiziert einen Block, in dem sich viele Elemente befinden, deren Ränge zwischen den Filtern liegen (Existenz nach dem Pigeon-Hole-Prinzip). Dieser Block wird dann mit Hilfe des Algorithmus A ( k - 1 ) nach einem guten Pivot-Element durchsucht . Der Rekursionsanker ist das triviale A ( 1 $p$$A(k)$$\varepsilon=1/k$$A(k)$$A(k-1)$$A(1)$Algorithmus. Die richtige Blockgröße (und die Berechnung) gibt Ihnen die oben angegebenen Laufzeit- und Platzanforderungen.

Übrigens, die Algorithmen, nach denen Sie suchen, wurden kürzlich als Algorithmen für konstanten Arbeitsraum bezeichnet .

Mir ist keine Untergrenze bekannt.