Struktura danych z wyszukiwaniem, wstawianie i usuwanie w zamortyzowanym czasie

Czy istnieje struktura danych umożliwiająca utrzymanie uporządkowanej listy, która obsługuje następujące operacje w zamortyzowanym czasie ? $O(1)$

GetElement (k) : zwraca ty element listy. $k$
InsertAfter (x, y) : Wstaw nowy element y do listy natychmiast po x.
Usuń (x) : Usuń x z listy.

W przypadku dwóch ostatnich operacji można założyć, że x jest podane jako wskaźnik bezpośrednio w strukturze danych; InsertElement zwraca odpowiedni wskaźnik dla y. InsertAfter (NULL, y) wstawia y na początku listy.

Na przykład, zaczynając od pustej struktury danych, następujące operacje aktualizują uporządkowaną listę, jak pokazano poniżej:

InsertAfter (NULL, a) $\implies$ [za]
InsertAfter (NULL, b) $\implies$ [b, a]
Wstaw po (b, c) $\implies$ [b, c, a]
Wstaw po (a, d) $\implies$ [b, c, a, d]
Usuń (c) $\implies$ [b, a, d]

Po tych pięciu aktualizacjach GetElement (2) powinien zwrócić d, a GetElement (3) powinien zwrócić błąd.

W optymalnych algorytmów list indeksowania i Subset Pozycja (1989) I znaleziono

rozwiązanie tego problemu.

Ω (\frac{l o g n}{l o g l o g n})

$\Omega{(\frac{log\ n}{log\ log\ n})}$

@Raphael: Myślę, że ma na myśli element, który nazwano by

gdyby struktura danych była tablicą. Tablice obsługują pierwszą operację w czasie

ale nie drugą; listy połączone obsługują drugą operację w czasie

ale nie pierwszą.

A [k]

$A[k]$

O (1)

$O(1)$

O (1)

$O(1)$

JeffE

Również zrównoważone drzewa binarne obsługują obie operacje w czasie

O (\log n)

$O(\log n)$

JeffE

@Raphael: Edytowane w celu wyjaśnienia.

JeffE

@JeffE tablica dynamiczna obsługuje pierwsze dwa w zamortyzowanym czasie

( cs.uwaterloo.ca/research/tr/1999/09/CS-99-09.pdf )

O (1)

$O(1)$

Diego

Odpowiedzi:

NIE.

Fredman i Saks udowodnili, że każda struktura danych, która obsługuje te operacje, wymaga co najmniej zamortyzowanego czasu na operację $\Omega(\log n/\log\log n)$ . (Jest to odniesienie [1] w artykule Dietza, o którym wspominasz w swoim pierwszym komentarzu.) Dolna granica zawiera bardzo wydajny model obliczeniowy sondy komórkowej, który uwzględnia tylko liczbę różnych adresów pamięci dostępnych przez aktualizację i zapytanie algorytmy.

Bez dodatkowych założeń dotyczących operacji aktualizacji i zapytań struktura danych Dietza jest najlepsza z możliwych (przynajmniej do stałych czynników).

JeffE
źródło

@AT: Ta granica nigdy nie „okazała się błędna”. Są sytuacje, w których nie ma zastosowania, ale jest to zupełnie inne stwierdzenie!

Raphael

@AT: Dolną granicę sortowania udowodniono w znacznie słabszym modelu obliczeń, a mianowicie w drzewach decyzyjnych binarnych. Granice „okazały się błędne” poprzez opracowanie szybszych algorytmów, których nie można określić jako binarne drzewa decyzyjne. Aby udowodnić, że dolna granica Fredmana i Saksa jest błędna, musisz zaprojektować szybszy algorytm, który nie ma dostępu do pamięci . Powodzenia.

JeffE

@JeffE i Raphael; przejrzyj moją drugą odpowiedź i potwierdź / odrzuć mój wynik, kiedy będziesz miał szansę. Dzięki.

Wygląda jak barierę pokonano modyfikując analizę z techniki chronogramu. $\Omega(\dfrac{\log n}{\log\log n})$

Nowa granica [dolna] została udowodniona dla podobnych problemów w modelu sonda-komórka [1]. Z lektury tego artykułu; rozumiem, że ta granica dotyczy również problemu reprezentacji listy . $\Omega(\log n)$

[1] Patrascu, Mihai i Erik D. Demaine. „Logarytmiczne dolne granice w modelu sondy komórkowej.” SIAM J. Comput. 35, nr 4 (kwiecień 2006 r.): 932–963. doi: 10.1137 / S0097539705447256.

W
źródło

Ω (\log n / \log \log n)

$\Omega(\log n/\log\log n)$

W rzeczy samej. Czy możesz również potwierdzić, że to ograniczenie dotyczy problemu reprezentacji listy ze słowami o stałej wielkości?

Θ (\log n / \log \log n)

$\Theta(\log n/\log \log n)$

Ω (\log n)

$\Omega(\log n)$