Ograniczone miejsce na algorytm wyboru?

Istnieje dobrze znany algorytm wyboru najgorszego przypadku do znalezienia -tego największego elementu w tablicy liczb całkowitych. Wykorzystuje podejście mediany-mediany, aby znaleźć wystarczająco dobrą oś przestawną, partycjonuje tablicę wejściową na miejscu, a następnie rekurencyjnie kontynuuje poszukiwania -tego największego elementu.k $O(n)$ $k$$k$

Co jeśli nie pozwolono by nam dotknąć tablicy wejściowej, ile dodatkowej przestrzeni byłoby potrzebne, aby znaleźć -ty największy element w czasie ? Czy możemy znaleźć -ty największy element w dodatkowej przestrzeni i nadal zachować czas działania ? Na przykład znalezienie maksymalnego lub minimalnego elementu zajmuje czas i przestrzeń . O ( n ) k O ( 1 ) O ( n ) O ( n ) O ( 1 $k$$O(n)$$k$$O(1)$$O(n)$$O(n)$$O(1)$

Intuicyjnie nie wyobrażam sobie, że moglibyśmy zrobić coś lepszego niż przestrzeń ale czy istnieje na to dowód?$O(n)$

Może wskazać kogoś do odniesienia lub wymyślić argument dlaczego „th Element wymaga miejsca można znaleźć w czasu?O ( n ) O ( n $\lfloor n/2 \rfloor$$O(n)$$O(n)$

Jest to otwarty problem, jeśli można dokonać wyboru z czasem i dodatkowymi komórkami pamięci O ( 1 ) bez zmiany danych wejściowych (patrz tutaj ). Ale możesz zbliżyć się do tego.$O(n)$$O(1)$

Munro i Ramana zaproponowano algorytm wyboru , która działa w czasu, przy użyciu tylko O ( 1 / ε ) dodatkowego miejsca (komórek). Ten algorytm pozostawia dane wejściowe bez zmian. Możesz wybrać dowolne małe ε > 0 .$O(n^{1+\varepsilon})$$O(1/\varepsilon)$$\varepsilon>0$

U podstaw algorytm Munro i Ramana działa jak klasyczny algorytm : utrzymuje lewą i prawą granicę (zwaną filtrem ), które są dwoma elementami o znanej randze. Żądany element jest zawarty między dwoma filtrami (pod względem rangi). Wybierając dobry element przestawny p , możemy sprawdzić wszystkie liczby względem filtrów i p . Umożliwia to aktualizację filtrów i zmniejsza liczbę elementów pozostałych do sprawdzenia (pod względem rangi). Powtarzamy, aż znajdziemy element żądania.$O(n)$$p$$p$

Różni się od klasycznego algorytmu wybór . Niech A ( k ) będzie algorytmem, który rozwiązuje wybór dla ε = 1 / k . Algorytm A ( k ) dzieli tablicę na bloki o jednakowych rozmiarach i identyfikuje blok, w którym znajduje się wiele elementów, których szeregi znajdują się między filtrami (istnienie według zasady gołębnika). Ten blok zostanie następnie przeskanowany w poszukiwaniu dobrego elementu przestawnego za pomocą algorytmu A ( k - 1 ) . Kotwicą rekurencyjną jest trywialna A ( 1 $p$$A(k)$$\varepsilon=1/k$$A(k)$$A(k-1)$$A(1)$algorytm. Odpowiedni rozmiar bloku (i wykonanie matematyki) zapewnia wymagania dotyczące czasu działania i miejsca, jak podano powyżej.

Btw, algorytmy, których szukasz, zostały ostatnio nazwane algorytmami stałej przestrzeni roboczej .

Nie znam żadnej dolnej granicy.