Czy unikalność elementu można rozwiązać w deterministycznym czasie liniowym?

9

Rozważ następujący problem:

Dane wejściowe : wyświetla liczb całkowitych $X,Y$

Cel : ustalenie, czy istnieje liczba całkowita $x$ która znajduje się na obu listach.

Załóżmy, że obie listy $X,Y$ mają rozmiar $n$ . Czy dla tego problemu istnieje deterministyczny algorytm czasu liniowego? Innymi słowy, czy możesz rozwiązać ten problem deterministycznie w czasie $O(n)$ bez losowości?

Niestety nie można założyć, że wszystkie elementy listy są małe.

Widzę, jak rozwiązać go w oczekiwanym czasie za pomocą algorytmu losowego: losowo wybierz 2-uniwersalną funkcję skrótu , zapisz elementy w tablicy mieszającej (używając jako funkcji skrótu), a następnie wyszukaj każdy element aby sprawdzić, czy znajduje się w tablicy mieszającej. Oczekiwany czas działania to . Jednak nie widzę, jak znaleźć algorytm deterministyczny z czasem działania . Jeśli spróbujesz to zdemandomizować i naprawić pojedynczą konkretną funkcję skrótu, pojawi się dane wejściowe najgorszego przypadku, które powodują uruchomienie tej procedury w $O(n)$ $h$ $X$ $h$ $Y$ $O(n)$ $O(n)$ $\Theta(n^2)$ czas. Najlepszy deterministyczny algorytm, jaki mogę znaleźć, polega na sortowaniu wartości, ale nie będzie to czas liniowy. Czy możemy osiągnąć liniowy czas pracy?

Widzę też, jak rozwiązać ten problem w czasie liniowym, jeśli założymy, że wszystkie elementy listy są liczbami całkowitymi z zakresu (w zasadzie sortuj według liczenia) - ale interesuje mnie to, co dzieje się ogólnie przypadek, gdy nie możemy tego założyć. $[1,n]$

Jeśli odpowiedź zależy od modelu obliczeniowego, model pamięci RAM przywołuje na myśl, ale interesują mnie wyniki dla każdego rozsądnego modelu obliczeniowego. Zdaję sobie sprawę z dolnych granic algorytmów drzewa decyzyjnego dla unikalności elementu , ale nie jest to ostateczne, ponieważ czasami możemy znaleźć algorytmy czasu liniowego, nawet jeśli istnieje związany w modelu drzewa decyzyjnego. $\Omega(n \log n)$ $\Omega(n \log n)$

algorithms complexity-theory lower-bounds

— DW
źródło

Tabele skrótów to O (n log n), ponieważ musisz obsługiwać kolizje.

— Thorbjørn Ravn Andersen

1

@ ThorbjørnRavnAndersen, nie widzę, skąd to otrzymujesz. Korzystanie z 2-uniwersalnych funkcji skrótu i odpowiedniej tabeli skrótów zapewnia, że liczba kolizji skrótu jest minimalna (z dużym prawdopodobieństwem), więc uważam, że czas działania jest osiągalny. Nie jestem pewien, skąd masz ; jeśli nie zrobisz czegoś specjalnego (np. użyj 2-uniwersalnego skrótu), najgorszym przypadkiem jest powodu kolizji.

O (n)

$O(n)$

O (n \lg n)

$O(n \lg n)$

O (n^{2})

$O(n^2)$

— DW

Diabeł tkwi w szczegółach, tutaj „stół haszujący o odpowiedniej wielkości”. Może się to okazać dość duże, jeśli nie chcesz kolizji. Typowym n-log-n jest (jeśli dobrze pamiętam) do obsługi kolizji funkcji skrótu z listą.

— Thorbjørn Ravn Andersen

1

@ ThorbjørnRavnAndersen Oczekiwana liczba kluczy mapowanych na ten sam adres jest stała (dla tabel, które nie są przeciążone), więc rodzaj rozwiązania kolizji jest nieistotny. Zobacz także tutaj . pasuje do najgorszego przypadku, jeśli używasz (zewnętrznych) zrównoważonych BST zamiast list.

O (n \log n)

$O(n \log n)$

— Raphael

1

Możesz rozwiązać problem w czasie liniowym, jeśli masz wystarczającą ilość pamięci, aby mieć bit dla każdej możliwej wartości w X i Y. Nie nakłada to żadnych ograniczeń w porządkowaniu X i Y.

Początkowo wszystkie bity są rozbrojone.
Iteruj przez X ustawiając odpowiedni bit.
Iteruj przez Y sprawdzając, czy odpowiedni bit został ustawiony powyżej.

— Thorbjørn Ravn Andersen
źródło

2

Niestety nie można założyć, że wszystkie liczby całkowite są małe (nie można założyć, że są wystarczająco małe, aby ten algorytm działał). W ogólnym przypadku czas działania tego algorytmu będzie wykładniczy w długości bitowej elementów listy. Ale dziękuję!

— DW

Nazwijmy to „macierzą bitów o odpowiedniej wielkości”. Również długość liniowa w bicie jest równoważna log-n. Czy poważnie myślisz o uzyskaniu wydajności logowania bez żadnych ograniczeń lub warunków wstępnych dla danych wejściowych?

— Thorbjørn Ravn Andersen

2

@ ThorbjørnRavnAndersen Przestrzeń ma długość wykładniczą w długości bitu (musisz zmapować wszystkie możliwe wartości), a czas jest liniowy w całkowitej wielkości listy (musisz spojrzeć na wszystkie wartości na obu listach). W długości bitów nic nie jest liniowe.

— wchargin

0

Ponieważ mówisz, że dwie listy zawierają liczby całkowite, myślę, że możemy uruchomić sortowanie radix na dwóch listach, a następnie przeprowadzić liniowe wyszukiwanie porównując dwie listy dla równoważnych elementów.

— anirudh
źródło

4

Działa to tylko wtedy, gdy istnieje ograniczenie wielkości liczb.

— Luke Mathieson

ale myślałem, że duża wielkość będzie problemem tylko przy liczeniu sortowania, a dla sortowania radix możemy wybrać wystarczająco wysoką podstawkę, aby rozwiązać ten problem ... proszę dać mi znać, czego tu brakuje

— anirudh

Co jeśli jedna z liczb to 2 ^ (2 ^ 128)?

— miniBill

@anirudh, ale wtedy masz inny algorytm dla różnych rozmiarów wejściowych - potrzebujesz większego alfabetu za każdym razem, gdy zwiększasz podstawkę, po prostu eksportujesz złożoność wzrastającej wielkości do zwiększenia wielkości alfabetu. Oczywiście jest to możliwe tylko w teorii, nie sądzę, aby dużo sprzętu pozwalało ci zmienić bazę, w której reprezentują liczby (możemy udawać na wejściach i wyjściach, ale sprowadza się to do (głównie) binarnego ).

— Luke Mathieson

0

Dlaczego nie wstawić liczb całkowitych z każdej listy do prostej operacji bitowej? Czy nie byłoby to optymalne w tym sensie, że , gdzie to średni rozmiar bitów liczb całkowitych; w szczególności nie widzę, jak można to zrobić lepiej, ponieważ zwykłe * przeczytanie * dwóch list zajęłoby tyle czasu. $\mathcal O\left(n\cdot \overline m\right)$ $\overline m$

— Realz Slaw
źródło

Dziękuję za twoją notatkę. Zobacz ostatni akapit pytania, który dotyczy tego punktu. W modelu RAM możesz odczytać dwie listy w czasie - nie zajmuje to czasu . I tu właśnie pojawia się model obliczeniowy - ta odpowiedź nie dowodzi, że deterministyczny czas liniowy jest niemożliwy.

O (n)

$O(n)$

O (n \cdot \overbar m)

$O(n \cdot \overbar{m})$

— DW

@DW W modelu RAM istnieje rozmiar słowa który jest stały, i ogranicza a zatem , co powoduje, że środowisko uruchomieniowe jest lub am Myliłem się?

w

$w$

m

$m$

\bar{m}

$\overline{m}$

O (n)

$\mathcal O\left(n\right)$

— Realz Slaw

hmm może rozważa stałej jest błędem.

w

$w$

— Realz Slaw

( nie jest uważane za stałe, ale zależne od : możesz mieć dowolną stałą wielokrotność tego, co jest konieczne do reprezentowania (wystarczająco szerokie, aby reprezentować ), po prostu nie dowolnie duże.)

w

$w$

n

$n$

m

$m$

n

$n$

n^{m}

$n^m$

— Greybeard

-1

Jest podobny do problemu unikatowości Elemeta, w którym masz zestaw liczb n i chcesz ustalić, czy wszystkie elementy są różne. Problem ma dolną granicę drzewa obliczeń algebraicznych . $O(n\log n)$

— Omer Gold
źródło

1

Pytanie jest dość jednoznaczne na temat liniowego czasu deterministycznego, a nie log-liniowego. Również w celu ustalenia, czy (nie na jakiej wartości) zestaw zawiera tylko unikalne elementy, które można wykonać szybciej niż loglinear.

— Zły

1

Czy masz na myśli

Ω (n \log n)

$\Omega(n\log n)$ ? Jeśli tak, może to sugerować, że problemu w pytaniu nie można rozwiązać w czasie liniowym. Ale samo powiedzenie, że pokrewny problem można rozwiązać w logarytmicznym czasie, tak naprawdę nie odpowiada na pytanie. (cc @EvilJS)

— David Richerby,

1

Dziękuję za twoją notatkę. Zastanawiam się, czy przegapiłeś ostatnie zdanie pytania. Powtórzę to tutaj: „Jestem tego świadomy

Ω (n \log n)

$\Omega(n \log n)$ dolne granice algorytmów drzewa decyzyjnego dla unikalności elementu , ale nie jest to ostateczne, ponieważ czasami możemy znaleźć algorytmy czasu liniowego, nawet gdy istnieje

Ω (n \log n)

$\Omega(n \log n)$ związany w modelu drzewa decyzyjnego. ”Innymi słowy, ta odpowiedź nie odpowiada na pytanie; po prostu powtarza coś, co już powiedziałem w pytaniu, o którym wiedziałem, ale które nie rozwiązuje pytania.

— DW

Można to zrobić w

O (n \log \log n)

$O(n \log \log n)$ czas, który jest lepszy niż dany

O (n \log n)

$O(n \log n)$ , więc jestem pewien, że tak nie było

Ω (n \log n)

$\Omega(n \log n)$ , ale to nie rozwiązuje pytania DW. Więc skomentuj tutaj.

— Zły