Kompromis czasowo-przestrzenny dla problemu brakującego elementu

Oto dobrze znany problem.

Biorąc pod uwagę tablicę $A[1\dots n]$ dodatnich liczb całkowitych, wyprowadzaj najmniejszą dodatnią liczbę całkowitą spoza tablicy.

Problem można rozwiązać w przestrzeni i czasie $O(n)$ : przeczytaj tablicę, śledź w przestrzeni $O(n)$ czy wystąpiło $1,2,\dots,n+1$ poszukaj najmniejszego elementu.

Zauważyłem, że możesz wymieniać przestrzeń na czas. Jeśli masz $O(\frac{n}{k})$tylko pamięć, możesz to zrobić w$k$rundach i uzyskać czas$O(k n)$. W szczególnym przypadku istnieje oczywiście algorytm kwadratowy o stałej przestrzeni.

Moje pytanie brzmi:

Czy jest to optymalny kompromis, tj. Czy $\operatorname{time} \cdot \operatorname{space} = \Omega(n^2)$ ? Ogólnie, w jaki sposób można udowodnić tego rodzaju granice?

Załóżmy model RAM z ograniczonym arytmetycznym i losowym dostępem do tablic w O (1).

Inspiracja do tego problemu: kompromis czasowo-przestrzenny dla palindromów w modelu z jedną taśmą (patrz na przykład tutaj ).

Można to zrobić za pomocą operacji na słowach $O(n \log n)$ i $O(1)$ słów pamięci (odpowiednio $O(n \log^2 n)$ i pamięć $O(\log n)$ w modelu pamięci RAM na poziomie bitów). Rzeczywiście, rozwiązanie będzie oparte na poniższej obserwacji.

Powiedzmy, że jest $n_0$ parzystych i $n_1$ nieparzystych liczb w zakresie $[1, n + 1]$ (więc $n_0 \approx n_1$ i $n_0 + n_1 = n + 1$ ). Następnie jest $b \in \{0, 1\}$ takie, że na wejściu jest co najwyżej $n_b - 1$ wartości z parzystością $b$ . Rzeczywiście, w przeciwnym razie istnieje co najmniej $n_0$parzyste i co najmniej $n_1$ nieparzyste wartości na wejściu, co oznacza, że ​​jest co najmniej $n_0 + n_1 = n + 1$ wartości na wejściu, sprzeczność (jest ich tylko $n$ ). Oznacza to, że możemy kontynuować wyszukiwanie brakującej liczby tylko wśród liczb nieparzystych lub parzystych. Ten sam algorytm można również zastosować do wyższych bitów notacji binarnej.

Nasz algorytm będzie wyglądał następująco:

1. Załóżmy, że już teraz, że są tylko $x$ wartości na wejściu z resztkowej modulo $2^b$ jest równe $r \in [0, 2^b)$ ale co najmniej $x + 1$ liczb w zakresie $[1, n + 1]$ , który ma reszta $r$ modulo $2^b$ (na początku wiemy, że na pewno dla $b = 0, r = 0$ ).

2. Powiedzmy, że na wejściu jest $x_0$ wartości z resztą $r$ modulo $2^{b + 1}$ i $x_1$ na wejściu z resztą $r + 2^b$ modulo $2^{b + 1}$ (możemy znaleźć te liczby w jednym przejściu przez wejście). Oczywiście $x_0 + x_1 = x$ . Ponadto, ponieważ na wejściu znajduje się co najmniej $x + 1$ liczb z resztą ( r , b + 1 )$r$ modulo$2^b$ , co najmniej jednego z pary$(r, b + 1), (r + 2^b, b + 1)$ spełnia wymagania kroku$1$ .

3. Znaleźliśmy brakującą liczbę, gdy $2^b \geqslant n + 1$ : jest tylko jedna liczba w zakresie $[1, n + 1]$ która może mieć resztę $r$ modulo $2^b$ ( samo $r$ , jeśli jest w zakresie), więc są na większość wartości zerowych na wejściu, które mają taką resztę. Więc $r$ jest rzeczywiście brakuje.

Oczywiście algorytm zatrzymuje się w krokach $O(\log n)$ , każdy z nich potrzebuje czasu $O(n)$ (pojedyncze przejście przez tablicę wejściową). Ponadto wymagane są tylko słowa pamięci $O(1)$ .

Jeśli rozumiem twoje definicje, można to zrobić w czasie liniowym ze stałą przestrzenią. Jest to oczywiście najniższa granica, ponieważ musimy przynajmniej odczytać całe wejście.

Odpowiedź udzielona w tym pytaniu jest satysfakcjonująca.

Niemożliwe jest uruchomienie tego z mniejszym czasem lub przestrzenią, a dodanie dodatkowego czasu lub przestrzeni jest bezużyteczne, więc nie ma tutaj kompromisu między czasoprzestrzenią. (Zauważ, że , więc zaobserwowany przez ciebie kompromis nie jest asymptotyczny.)$n=O(n/k)$

Jeśli chodzi o twoje ogólne pytanie, nie znam żadnych fajnych twierdzeń, które pomogą ci udowodnić kompromisy czasoprzestrzenne. To pytanie wydaje się wskazywać, że nie ma (znanej) łatwej odpowiedzi. Gruntownie:

Przypuśćmy, że część języka jest rozstrzygalne w czasu (za pomocą pewnej ilości przestrzeni) i y przestrzeń (stosując pewną ilość czasu). Można znaleźć , f , g , tak że L jest rozstrzygalne przez M , która biegnie w f ( t , s ), czasu i g ( t , s $t$$s$$f,g$$L$$M$$f(t,s)$$g(t,s)$ ?

jest nieznany, a silna odpowiedź rozwiązałaby wiele otwartych problemów (w szczególności dotyczących SC), co sugeruje, że nie ma łatwego rozwiązania.

EDYCJA: Ok, z powtarzaniem (ale nadal zakładam, że przy wejściu o wielkości maksymalna możliwa liczba to n + $n$$n+1$ ).

Zauważ, że nasz algorytm musi być w stanie rozróżnić co najmniej możliwych odpowiedzi. Załóżmy, że przy każdym przejściu danych możemy uzyskać maksymalnie k części danych. Następnie będziemy potrzebować n / k przepustek, aby rozróżnić wszystkie odpowiedzi. Zakładając, że k = n / s, wówczas biegniemy w $n$$k$$n/k$$k=n/s$$\frac{n}{n/s}n=sn$ czas. Myślę więc, że to potwierdza, czego chcesz.

Trudność polega na wykazaniu, że za każdym razem otrzymujemy tylko bitów. Jeśli założysz, że naszą jedyną legalną operacją jest =, to jesteśmy dobrzy. Jeśli jednak zezwolisz na bardziej złożone operacje, będziesz w stanie uzyskać więcej informacji.$k$