Dolne granice dla struktur danych

14

Czy znane są wyniki, które wykluczają istnienie struktur danych „zbyt dobrych, by były prawdziwe”?

Na przykład: czy można dodać funkcjonalność $Split$ i do struktury danych obsługi zamówień (patrz Dietz i Sleator STOC '87 ) i nadal uzyskiwać operacje czasowe ? $Join$ $\mathcal{O}(1)$

Lub: czy można zaimplementować uporządkowany zestaw z kluczami całkowitymi i operacjami czasowymi ? Oczywiście jest to co najmniej tak trudne, jak znalezienie liniowego algorytmu czasowego do sortowania liczb całkowitych. $\mathcal{O}(1)$

Czy odpowiedzią okazał się być nie na jedno z tych pytań? Czy wyniki dolnej granicy są znane dla jakiejkolwiek naturalnej struktury danych?

ds.data-structures big-list lower-bounds time-complexity Shaun Harker
źródło

Wszystko się zmienia, jeśli jesteśmy w stanie dodać ograniczenia do przestrzeni problemowej. Na przykład, jeśli mamy ograniczony zestaw kluczy i wystarczającą ilość pamięci, możemy je posortować w czasie liniowym za pomocą wektora bitowego.

jetru

1

Myślę, że powodem, dla którego nie otrzymujesz zbyt wielu odpowiedzi na to pytanie, jest to, że jest tak wiele możliwości. Wiele, wiele struktur danych znało dolne granice i trudno nie tylko się o nie potknąć. Wyszukiwarka Google „dolnej granicy” „struktury danych” obejmuje dla mnie 5 artykułów, o których jeszcze nie wspomniano w tym wątku. Myślę, że odniesienie większego sukcesu uzyskałoby odpowiedź, gdybyś ją ograniczył, być może usuwając część o „naturalnych strukturach danych” i po prostu pytając o utrzymanie listy lub uporządkowane liczby całkowite (ale nie jedno i drugie w jednym pytaniu).

jbapple,

Pominąłem, że 5 artykułów, które znalazłem w wyszukiwarce Google, znajdowało się tylko na pierwszej stronie wyników wyszukiwania.

jbapple,

@jbapple: Masz rację! Myślę, że kliknięcia osób z tej społeczności, które próbują mi pomóc w zadaniu pytania, sprawiły, że dobre wyniki znalazły się na szczycie listy. (Na przykład ta strona znajduje się teraz na liście!) Nie przypominam, aby była użyteczna, kiedy przeprowadzałem wyszukiwanie, lub prawdopodobnie ograniczyłbym to pytanie, jak sugerujesz. (Lub byłem wielkim manekinem, to też jest możliwe.))

Shaun Harker

19

Jest naprawdę miła rozmowa na dynamicznych dolnych granic na wykresach Mihai Pătraşcu. Podsumowując (na str. 20 slajdów), mamy dolne granice pod względem czasu zapytania i czasu aktualizacji (wstaw krawędź): $t_q$ $t_u$

wprowadź opis zdjęcia tutaj

Szczegółowe informacje można znaleźć w dokumencie . Niektóre inne dokumenty Mihai są również istotne i miłe.

AKTUALIZACJA: Odkryłem, że jego praca doktorska „ Techniki dolnej granicy dla struktur danych ” zapewnia dolne granice dla wielu problemów z centralną strukturą danych przy użyciu opracowanych przez niego technik. Z pewnością warto przeczytać.

Hsien-Chih Chang 張顯之
źródło

1

Ta praca jest cudowna, dziękuję bardzo za udostępnienie linku.

Shaun Harker

6

Odpowiedź na dowolne pytanie zależy od modelu obliczeniowego. Na przykład na wielu komputerach mnożenie liczb całkowitych jest droższe niż ich dodawanie. Niektóre modele odzwierciedlają to, a niektóre nie.

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

jbapple
źródło

Ładny. Ale wygląda na to, że przeceniłeś wynik w pracy Anderssona i Thorupa. Odnosi się to tylko do struktur przestrzeni liniowej, a nie wszystkich wielomianowych struktur przestrzeni.

Shaun Harker,

2

Andersson i Thorup cytują Beame i Ficha dla przestrzeni wielomianowej: „Dolna granica wynika z wyniku Beame i Ficha. Pokazuje to, że nawet jeśli chcemy po prostu obsługiwać operacje wstawiania i poprzedników w przestrzeni wielomianowej, jedna z tych dwóch operacji ma najgorszy przypadek Ω (sqrt (log n / log log n)), pasujący do naszej wspólnej górnej granicy. Zauważamy, że można znaleźć lepsze granice i kompromisy dla niektórych poszczególnych operacji. Rzeczywiście, będziemy wspierać min, max, poprzednik, następca i operacja usuwania w stałym czasie, a wstawianie i wyszukiwanie odbywa się tylko w czasie Θ (sqrt (log n / log log n)). ”

jbapple,

Widzę, że liniowa przestrzeń wkracza do reklamowania górnej granicy , ale następstwo 3.10 Beame i Ficha daje wieloprzestrzenną dolną granicę , jak pan powiedział, a ja głupio zaprzeczałem. Przyszło mi też do głowy, że można chcieć reklamować najgorsze przypadki dla górnych granic, a reklamy amortyzować dla dolnych granic. Artykuł Anderssona i Thorupa rzeczywiście cytuje (strona 5) Beame i Fich dla zamortyzowanej dolnej (i górnej) granicy. Ale wniosek 3.10 wydaje się wyznaczać dolną granicę dla najgorszego przypadku. Być może ktoś też mógłby mi o tym podpowiedzieć?

Shaun Harker,

2

$O(n \log n)$

Ponadto nie jest niczym niezwykłym stosowanie argumentów teorii informacji (np. Złożoności Kołmogorowa) w celu udowodnienia niższych granic struktur danych.

chazisop
źródło

Dolne granice dla struktur danych

Odpowiedzi: