Struktura danych z wyszukiwaniem, wstawianie i usuwanie w zamortyzowanym czasie

25

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) [za]
  • InsertAfter (NULL, b) [b, a]
  • Wstaw po (b, c) [b, c, a]
  • Wstaw po (a, d) [b, c, a, d]
  • Usuń (c) [b, a, d]

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

W
źródło
2
W optymalnych algorytmów list indeksowania i Subset Pozycja (1989) I znaleziono rozwiązanie tego problemu. Ω(log nlog log n)
AT
2
@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 O ( 1 ), ale nie drugą; listy połączone obsługują drugą operację w czasie O ( 1 ), ale nie pierwszą. A[k]O(1)O(1)
JeffE
2
Również zrównoważone drzewa binarne obsługują obie operacje w czasie . O(logn)
JeffE
1
@Raphael: Edytowane w celu wyjaśnienia.
JeffE
2
@JeffE tablica dynamiczna obsługuje pierwsze dwa w zamortyzowanym czasie ( cs.uwaterloo.ca/research/tr/1999/09/CS-99-09.pdf )O(1)
Diego

Odpowiedzi:

33

NIE.

Fredman i Saks udowodnili, że każda struktura danych, która obsługuje te operacje, wymaga co najmniej zamortyzowanego czasu na operacjęΩ(logn/loglogn) . (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
3
@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
5
@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.
AT
6

Wygląda jak barierę pokonano modyfikując analizę z techniki chronogramu.Ω(lognloglogn)

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 .Ω(logn)


[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
1
Ω(logn/loglogn)
W rzeczy samej. Czy możesz również potwierdzić, że to ograniczenie dotyczy problemu reprezentacji listy ze słowami o stałej wielkości?
AT
1
Θ(logn/loglogn) Ω(logn)