Utrzymanie porządku na liście w w Czas

15

Problem z utrzymaniem porządku (lub „utrzymaniem porządku na liście”) polega na obsłudze operacji:

  • singleton: tworzy listę z jednym elementem, zwraca do niej wskaźnik
  • insertAfter: dany wskaźnik do elementu wstawia nowy element po nim, zwracając wskaźnik do nowego elementu
  • delete: dany wskaźnik do elementu usuwa go z listy
  • minPointer: biorąc pod uwagę dwa wskaźniki do elementów na tej samej liście, zwraca jeden bliżej początku listy

Znam trzy rozwiązania tego problemu, które wykonują wszystkie operacje w zamortyzowanym czasie . Wszystkie używają mnożenia.O(1)

Czy można utrzymywać porządek na liście w zamortyzowanym czasie bez użycia operacji arytmetycznych poza ?O(1)ZAdo0

jbapple
źródło
ZAdo0
ZAdo0ZAdo0
Znalazłem, gdzie o tym czytałem; chodziło o Pentium 4, a nie III; i nie wdrożyło multiplikacji, zamiast tego pracowało nad tym z nową instrukcją tego procesora: M. Thorup, „O implementacjach AC0 drzew syntezy jądrowej i hałd atomowych”, w toku czternastego dorocznego sympozjum ACM-SIAM na temat algorytmów dyskretnych w Filadelfii, PA, USA, 2003, s. 699–707.
AT

Odpowiedzi: