Wymagania dotyczące pamięci dla wyboru mediany (algorytmy dwuprzebiegowe)

W klasycznej pracy Munro i Paterson badają problem ilości pamięci potrzebnej algorytmowi do znalezienia mediany w losowo posortowanej tablicy. W szczególności koncentrują się na następującym modelu:

wejście jest odczytywane od lewej do prawej kilka razy P.

Pokazano, że komórki pamięci są wystarczające, ale odpowiadająca dolna granica jest znana tylko dla P = 1. Nie widziałem żadnego wyniku dla P> 1. Czy ktoś jest świadomy takich dolnych granic? $O(n^{\frac{1}{2P}})$

Zauważ, że główna trudność polega na tym, że przy drugim przejściu dane wejściowe nie są już losowo uporządkowane.

Wypróbuj ten artykuł Chana w najnowszej wersji SODA: http://portal.acm.org/citation.cfm?id=1721842&dl=ACM .

Szybkie wyszukiwanie Google również znalazło następujący artykuł, który wydaje się być odpowiedni, ale go nie przeczytałem: http://portal.acm.org/citation.cfm?id=1374470 .

Pierwszą kartą, która potwierdziła granice więcej niż 1 przepustki, była moja praca z Jayram i Amitem z SODA'08. Jest też papier, o którym wspomniał Warren, który poprawia granice czystszym dowodem.

Krótko mówiąc, rozumiemy zależność, jeśli dopuścisz stałe przed liczbą przebiegów. Oczywiście, te stałe są w potęgie wykładniczej, więc możesz poprosić o dokładne zrozumienie. Moja główna skarga polega na tym, że model przesyłania strumieniowego w wielu kanałach nie jest tak dobrze zmotywowany.

Bardziej intrygujące pytanie brzmi, czy możemy udowodnić dolną granicę programu rozgałęziającego. Czy to możliwe, że nawet w przypadku algorytmu z ograniczoną przestrzenią, który może uzyskiwać dostęp do pamięci według własnego uznania, najlepszą strategią jest po prostu przesyłanie strumieniowe w wielu kanałach?

Odpowiedź wydaje się twierdząca i mamy częściowy postęp w kierunku jej udowodnienia.