Struktura danych oparta na porównaniu do znajdowania pozycji

Czy istnieje struktura danych, która pobiera nieuporządkowaną tablicę elementów, wykonuje wstępne przetwarzanie w i odpowiada na zapytania: czy na liście jest jakiś element , każde zapytanie w najgorszym czasie ? $n$ $O(n)$ $x$ $O(\log n)$

Naprawdę uważam, że nie ma, dlatego mile widziany jest również dowód, że nie ma.

ds.data-structures sorting

— Chi-Lan
źródło

(1) Nie wiem, dlaczego możesz powiedzieć „Oczywiście, że biorę pod uwagę oczekiwany czas”, ponieważ w swoim pytaniu nie podajesz słowa „oczekiwany”. Spróbuj sformułować swoje pytanie bardziej precyzyjnie, zanim powiesz „oczywiście”. (2) Zdefiniuj „nieukrywalny”.

— Tsuyoshi Ito

(1) Rozumiem. Dziękuję za wyjaśnienie. Gdyby ktoś zapytał „Czy zależy Ci na czasie działania?”, Odpowiedź brzmiałaby „oczywiście”. :) :) (2) Myślę, że „Jedynym dozwolonym działaniem jest porównanie dwóch wartości na liście” jest znacznie bardziej precyzyjne niż tylko stwierdzenie „niemożliwy do mieszania”. Czy możesz edytować pytanie, aby ludzie nie musieli czytać komentarzy, aby zrozumieć, co oznacza „nieukrywalny”?

— Tsuyoshi Ito,

Nawiasem mówiąc, jeśli nie możesz tego udowodnić, dlaczego wiesz, że to niemożliwe? Jeśli jest to ćwiczenie z podręcznika lub zajęć, pytasz na niewłaściwej stronie internetowej.

— Tsuyoshi Ito,

Czy to twoje pytanie: czy istnieje struktura danych, która pobiera nieuporządkowaną tablicę n elementów, wykonuje wstępne przetwarzanie w O (n) i odpowiada na pytania: czy na liście jest jakiś element x, każde zapytanie w najgorszym czasie O (log n)?

— sdcvvc,

@Filip: Czy łatwo to zobaczyć? Jeśli to prawda, zgadzam się, że rozwiązuje to pytanie.

— Tsuyoshi Ito

Odpowiedzi:

Oto dowód, że to niemożliwe. Załóżmy, że możesz zbudować taką strukturę danych. Zbuduj to. Następnie wybierz losowo elementów z listy, dodaj do każdego z nich, gdzie jest mniejsza niż różnica między dowolnymi dwoma elementami na liście, i wykonaj zapytania, aby sprawdzić, czy którykolwiek z wynikowych elementów jest na liście. Do tej pory wykonałeś zapytania . $n/\log n$ $\epsilon$ $\epsilon$ $O(n)$

Chciałbym twierdzić, że dokonane porównania są wystarczające, aby stwierdzić, czy element na oryginalnej liście jest mniejszy lub większy niż jakikolwiek nowy element . Załóżmy, że nie możesz powiedzieć. Ponieważ jest to model oparty na porównaniu, nie wiadomo, czy było równe czy nie, co jest sprzeczne z założeniem, że struktura danych działa. $a$ $b$ $a$ $b$

Teraz, ponieważ elementów, które wybrałeś, były losowe, twoje porównania z dużym prawdopodobieństwem dały wystarczającą ilość informacji, aby podzielić oryginalną listę na list każdej wielkości . Sortując każdą z tych list, otrzymujesz losowy algorytm sortowania w czasie oparty wyłącznie na porównaniach, co jest sprzecznością. $n/\log n$ $n/\log n$ $O(\log n)$ $O(n \log \log n)$

— Peter Shor
źródło

Kilka wskazówek pomocnych w zrozumieniu dowodu (zakładając, że sam rozumiem go poprawnie): elementy powinny być wypełnione elementami po dodaniu do nich ; model porównawczy gwarantuje, że wiesz, w których przypadkach i ; listy są w porządku rosnącym: każdy element na dowolnej wyższej liście jest wyższy niż każdy element na dowolnej dolnej liście; po oryginalnych zapytaniach masz wystarczającą ilość informacji, aby utworzyć listy wokół pozycji, które losowo wybrałeś,

b

$b$

ϵ

$\epsilon$

a \leq b

$a \leq b$

a \geq b

$a \geq b$

n / \log n

$n / \log n$

— Alex ten Brink

(ciąg dalszy) zauważ, że nie musisz nawet być w stanie zbudować listy w przewidzianym czasie, aby dowód mógł zostać przetrzymany.

— Alex ten Brink

Nie rozumiem tego dowodu. Ostateczna sprzeczność jest wyłączona „algorytm oparty wyłącznie na porównaniach”, ale w pierwszych krokach naszego algorytmu dodaliśmy do każdej pozycji (dalej, „gdzie jest mniejsza niż różnica między dowolnymi dwoma pozycjami na liście”). Dlaczego nadal jesteśmy uzasadnieni, że nasz algorytm nadal opiera się na porównaniu tylko wtedy, gdy założymy, że nasze produkty mają niedyskretne całkowite zamówienie?

ϵ

$\epsilon$

ϵ

$\epsilon$

— Artem Kaznatcheev

@Artem: Twój oryginalny wejściowy składa się z elementów . Następnie konstruujesz nowy zestaw ; reprezentujesz oryginalny jako i zmodyfikowany jako . Teraz używasz algorytmu czarnej skrzynki; algorytm porównuje elementy ze sobą; odpowiedzieć na takie pytania, wystarczy porównać liczbę stałą elementów do siebie. Stąd wszystko powinno być wykonalne w modelu porównawczym ze stałym narzutem.

x \in X

$x \in X$

X^{'} = X \times {0, 1}

$X' = X \times \{0,1\}$

x \in X

$x \in X$

(x, 0) \in X^{'}

$(x,0) \in X'$

x + ϵ

$x + \epsilon$

(x, 1) \in X^{'}

$(x,1) \in X'$

X^{'}

$X'$

X

$X$

— Jukka Suomela

@Aryabhata: tak. Co to jest algorytm ?

O (\log^{2} n)

$O(\log^2 n)$

— Peter Shor,

Wierzę, że tutaj jest inny dowód, dowodzący niemożność struktury czasu zapytania z wstępnym przetwarzaniem . $\mathcal{O}(\log ^k n)$ $\mathcal{O}(n)$

Załóżmy, że podczas wstępnego przetwarzania dokonujesz porównań , prowadząc do częściowej kolejności. $\mathcal{O}(n)$

Rozważmy teraz rozmiar największego antichaina. Ponieważ te elementy nie są porównywalne, abyśmy mieli algorytm zapytania , musimy mieć taki . $A$ $\mathcal{O}(\log ^k n)$ $A = \mathcal{O}(\log ^k n)$

Według twierdzenia Dilwortha istnieje podział wielkości na łańcuchy. $A$

Teraz możemy uzupełnić algorytm w celu ustalenia łańcuchów w partycji. Możemy ustalić, czy dwa elementy są porównywalne, tworząc ukierunkowany wykres porównań i wykonując analizę osiągalności. Można to zrobić bez żadnych dodatkowych porównań. Teraz po prostu brutalnie wymuś każdą możliwą partycję rozmiaru aby ustalić, czy jest to partycja łańcuchów. $A$

Po uzyskaniu łańcuchów możemy je połączyć, aby uzyskać algorytm porównań do sortowania całej listy. $\mathcal{O}(n \log \log n)$

— Aryabhata
źródło

To niezły pomysł. A jeśli potrafisz pokazać, że partycja łańcuchowa musi być znana algorytmowi, możesz użyć scalesort, aby pokazać, że potrzeba tylko dodatkowych porównań O (n log log n), aby posortować całe dane wejściowe, a nie Jensen. Ale jest problem: dlaczego algorytm przetwarzania wstępnego musi skonstruować partycję łańcuchową? Tak, partycja łańcuchowa musi istnieć, ale to bardzo różni się od tego, że jest znana algorytmowi.

— David Eppstein,

O (n \log \log n)

$O(n\log\log n)$

Ω (n \log n)

$\Omega(n\log n)$

Ω (n)

$\Omega(n)$

@Yuval: może powinieneś napisać to spostrzeżenie jako rzeczywistą odpowiedź, ponieważ wydaje mi się, że musisz wykonać umiarkowaną ilość pracy, aby uzyskać powyższy wynik z dowodów w odpowiedziach.

— Peter Shor,

Ω (n \log n)

$\Omega(n \log n)$

Ω (n^{1 - ϵ})

$\Omega(n^{1-\epsilon})$

ϵ

$\epsilon$

o (n \log n)

$o(n \log n)$

O (n / \log n)

$O(n / \log n)$

\log n

$\log n$

n / \log n

$n/\log n$

θ (n \log \log n)

$\theta(n \log\log n)$

$k<n$ $Θ(n \log k)$ $n$ $c>0$ $c \, n \log k$ $≤c \, n \log k/k$ $k' = k / \log k ≤ n/\log n$ $O(n \log k') = O(n \log k)$ czas, który pozwala na koszt zapytania . $O(n/k')$

W szczególności, stosując wstępne przetwarzanie , nie możemy mieć kosztu zapytania . Ponadto przetwarzanie wstępne odpowiada w dla każdego a zatem koszt zapytania . $O(n)$ $o(n)$ $o(n \log n)$ $k$ $O(n^ε)$ $ε>0$ $Ω(n^{1−ε})$

— Dmytro Taranovsky
źródło