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 ?
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
źródło
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/logn ϵ ϵ 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.b a ba 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 O ( log n ) O ( n log log n )n/logn n/logn O(logn) O(nloglogn)
źródło
Wierzę, że tutaj jest inny dowód, dowodzący niemożność struktury czasu zapytania z wstępnym przetwarzaniem O ( n ) .O(logkn) O(n)
Załóżmy, że podczas wstępnego przetwarzania dokonujesz porównań , prowadząc do częściowej kolejności.O(n)
Rozważmy teraz rozmiar największego antichaina. Ponieważ te elementy nie są porównywalne, abyśmy mieli algorytm zapytania O ( log k n ) , musimy mieć taki A = O ( log k n ) .A O(logkn) A=O(logkn)
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.O(nloglogn)
źródło
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(nlogn) k O(nε) ε>0 Ω(n1−ε)
źródło