Określanie konkretnej liczby w czasie i przestrzeni (najgorszy przypadek)

$\newcommand\ldotd{\mathinner{..}}$ Biorąc pod uwagę, że $A[1\ldotd n]$ to liczby całkowite takie, że $0\le A[k]\le m$ dla wszystkich $1\le k\le n$ oraz występowanie każdego liczba z wyjątkiem określonej liczby w $A[1\ldotd n]$ jest liczbą nieparzystą. Spróbuj znaleźć numer, którego wystąpienie jest liczbą parzystą.

Istnieje algorytm $\Theta(n\log n)$ : sortujemy $A[1\ldotd n]$ na $B[1\ldotd n]$ i $B[1\ldotd n]$ na wiele części, których wartość elementów to to samo, dlatego możemy policzyć występowanie każdego elementu.

Chcę znaleźć najgorszy przypadek - $O(n)$ -czas-i- $O(n)$ -przestrzeń.

Załóżmy, że $m=\Omega(n^{1+\epsilon})$ i $\epsilon>0$ , dlatego sortowanie radix jest niedopuszczalne. $\DeclareMathOperator{\xor}{xor}$ Binarne operacje bitowe są dopuszczalne, na przykład $A[1]\xor A[2]$ .

algorithms search-algorithms

— Yai0Phah
źródło

Odpowiedź Aryabhaty poniżej pokazuje, że ogólny przypadek nie jest dobry, ale może masz jeszcze inne ograniczenia? Prostym (ale dużym) ograniczeniem byłoby wymuszenie, aby wszystkie wpisy w tablicy miały rozmiar

O (n)

$O(n)$ . Dałoby to dość trywialny algorytm liniowy.

— Luke Mathieson,

@LukeMathieson: Usunąłem tę odpowiedź, ponieważ nie jestem jeszcze przekonany, że cytowany artykuł będzie działał bez żadnych modyfikacji, a poza tym OP wydaje się zainteresowany jedynie modelem pamięci RAM o jednolitym koszcie.

— Aryabhata

@Aryabhata: hehe, cóż, odpowiedzi tam nie ma! Co ciekawe i być może przydatne dla Franka, jaki według ciebie był problem z adaptacją wyniku w gazecie? Szybkie przeglądanie sugerowało, że się zastosowało, ale oczywiście nie przeczytałem w nim.

— Luke Mathieson

@LukeMathieson: Fakt, że inne elementy muszą pojawiać się nieparzystą liczbę razy w bieżącym problemie. Odtąd też przejrzałem dowód ...

— Aryabhata,

Byłoby interesujące, jeśli interesują Cię wyniki teoretyczne lub praktyczne rozwiązania. Z punktu widzenia teorii, moja pierwsza reakcja jest szybkie, że można sortować listę liczb całkowitych szybciej niż . Istnieje deterministyczny algorytm Hana, który działa w czasie . W przypadku algorytmów losowych znane są jeszcze lepsze wyniki, np. Han i Thorup znaleźli algorytm . Myślę jednak, że twój problem nie powinien wymagać sortowania.

O (n \log n)

$O(n\log n)$

O (\log \log n)

$O(\log\log n)$

O (n \sqrt{\log \log n})

$O(n \sqrt{\log\log n})$

— A.Schulz

Odpowiedzi:

Oto pomysł na prosty algorytm; po prostu policz wszystkie wystąpienia!

Znajdź . - czas $m = \max A$ $\Theta(n)$
Tablica „ ” . - czas ¹ $C[0..m]$ $O(1)$
Iteruj nad i zwiększaj o jeden, ilekroć znajdziesz . Jeśli to , dodać liniowej lista . - czas $A$ $C[x]$ $A[\_]=x$ $C[x]$ $0$ $x$ $L$ $\Theta(n)$
Iteruj po i znajdź element z nawet. - czas . $L$ $x_e$ $C[x_e]$ $O(n)$
Zwróć . $x_e$

Podsumowując, daje to algorytm czasu liniowego, który może wykorzystywać (w sensie alokacji) dużo pamięci. Zauważ, że kluczowa jest tutaj możliwość losowego dostępu do w stałym czasie niezależnie od . $C$ $m$

Dodatkowe związane z przestrzenią jest trudniejsze przy takim podejściu; Nie znam żadnej struktury danych słownikowej, która oferuje wyszukiwanie czasu . Możesz użyć tablic skrótów, dla których tutaj są implementacje z oczekiwanym czasem wyszukiwania ( rozmiar tabeli, liczba przechowywanych elementów), dzięki czemu można uzyskać dowolnie dobrą przestrzeń liniową - w oczekiwaniu. Jeśli wszystkie wartości w mapie odwzorowują tę samą wartość skrótu, zostaniesz wkręcony. $O(n)$ $O(1)$ $O(1 + k/n)$ $n$ $k$ $A$

W pamięci RAM odbywa się to domyślnie; wszystko czego potrzebujemy to pozycja początkowa i być może pozycja końcowa.

— Raphael
źródło

Niemal trywialnym rozwiązaniem - które wykorzystuje jednak przestrzeń - jest użycie mapy skrótu. Przypomnij sobie, że mapa haszowa zamortyzowała środowisko uruchomieniowe do dodawania i wyszukiwania elementów. $\Theta(n)$ $\mathcal{O}(1)$

Dlatego możemy zastosować następujący algorytm:

Przeznaczyć hash mapę . Iteracyjnego . Dla każdego elementu zwiększ liczbę zaobserwowanych wystąpień, tj. . $H$ $A$ $i \in A$ $H(i)++$
Iteruj przez zestaw kluczy mapy skrótów i sprawdź, który z kluczy ma parzystą liczbę wystąpień.

Teraz jest to prosty algorytm, który tak naprawdę nie używa żadnej dużej sztuczki, ale czasami nawet to wystarcza. Jeśli nie, możesz sprecyzować, jakie ograniczenia przestrzeni nakładasz.

— HdM
źródło

Wciąż chciałbym wiedzieć, czy istnieje nielosowy algorytm czasowy wykorzystujący przestrzeń wielomianową. W szczególności, czy istnieją jakieś teoretyczne dowody na to, że znalezienie jedynego występującego w parze przedmiotu jest trudniejsze niż znalezienie jedynego nieparzystego przedmiotu?

O (n)

$O(n)$

— A.Schulz

@ A.Schulz Myślę, że jest to algorytm czasu oczekiwanego przy użyciu tabeli skrótów. Pamiętam, że ktoś powiedział mi algorytm (lub w specjalnym przypadku, powiedzmy, nieparzysty = 1, a nawet = 2) może ze stosem, ale nie pamiętam go.

O (n)

$O(n)$

O (n)

$O(n)$

— Yai0Phah

Nie każda implementacja hashtable ma tę właściwość; zwykle wyszukiwanie nie jest , nawet nie amortyzowane (afaik). W rzeczywistości wcześniejsza dyskusja nie przyniosła żadnej implementacji, która ma ciągłe wyszukiwanie czasu. Czy mógłbyś to sprecyzować?

O (1)

$O(1)$

— Raphael