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 ).

complexity-theory time-complexity space-complexity

— sdcvvc
źródło

Nie, możesz posortować tablicę w

a następnie znaleźć brakującą liczbę (pierwsza liczba powinna wynosić 1, druga powinna wynosić 2, ... w przeciwnym razie znajdziesz) w O (n), to sortowanie można wykonać z miejscowym połączeniem oznacza

dodatkową spację, więc czas

spacja należy do

O (n \log n)

$O(n \log n)$

O (1)

$O(1)$

\cdot

$\cdot$

O (n \log n)

$O(n \log n)$ . Nie wiem, czy mam twój problem dokładnie, czy nie (z tego powodu nie odpowiedziałem, a także nie wiem, czy jest lepszy związek).

Zakładam, że dane wejściowe są tylko do odczytu. (Jeśli nie jest, problem można optymalnie rozwiązać w przestrzeni

czas / przestrzeń

: pomnóż wejście przez 2 i użyj parzystości, aby zasymulować

O (n)

$O(n)$

O (1)

$O(1)$

O (n) / O (n)

$O(n)/O(n)$ algorytm )

— sdcvvc

Jaki jest algorytm stałej przestrzeni? Wygląda na to, że potrzebujesz

miejsca na

\log n

$\log n$

n^{2}

$n^2$ która jest dla mnie „oczywista”

— Xodarap,

W tym modelu liczby całkowite wielkości słów przyjmują

; jeśli jest to wygodniejsze, możesz odpowiedzieć na dowolny wariant pytania z

O (1)

$O(1)$

dla pewnej stałej

time \cdot space = Ω (\frac{n^{2}}{\log^{k} n})

$\operatorname{time} \cdot \operatorname{space} = \Omega(\frac{n^2}{\log^k n})$

k

$k$

— sdcvvc,

@ sdcvvc, nie rozumiem twojego algorytmu

, czy mógłbyś opisać go nieco bardziej? (zwróć uwagę, że wczytywanie do bitów zajmuje

O (n) / O (1)

$O(n)/O(1)$

O (\log n)

$O(\log n)$

Odpowiedzi:

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:

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$ ).
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$ modulo $2^b$ , co najmniej jednego z pary $(r, b + 1), (r + 2^b, b + 1)$ spełnia wymagania kroku $1$ .
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)$ .

— Kaban-5
źródło

Cieszę się, że po tym czasie odpowiedź została udzielona :)

— sdcvvc,

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 przestrzeń (stosując pewną ilość czasu). Można znaleźć , tak że jest rozstrzygalne przez , która biegnie w czasu i $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+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 części danych. Następnie będziemy potrzebować przepustek, aby rozróżnić wszystkie odpowiedzi. Zakładając, że 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$

— Xodarap
źródło

Połączone pytanie zakłada, że każdy numer pojawia się najwyżej raz. Nie przyjmuję tego założenia, więc rozwiązanie nie ma zastosowania. Dziękujemy za drugi link.

— sdcvvc

@sdcvvc: Mój błąd, zakładam, że używasz wersji, którą znam. Nie mam pełnej odpowiedzi, ale komentarz jest za długi - mam nadzieję, że moja edycja przyda się.

— Xodarap,

k

$k$

2^{k}

$2^k$

n / 2^{k}

$n/2^k$

n / k

$n/k$