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źnikinsertAfter
: dany wskaźnik do elementu wstawia nowy element po nim, zwracając wskaźnik do nowego elementudelete
: dany wskaźnik do elementu usuwa go z listyminPointer
: 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.
- Athanasios K. Tsakalidis: Utrzymanie porządku na uogólnionej liście powiązanej
- Dietz, P., D. Sleator, Dwa algorytmy utrzymywania porządku na liście
- Michael A. Bender, Richard Cole, Erik D. Demaine, Martin Farach-Colton i Jack Zito, „Dwa uproszczone algorytmy utrzymania porządku na liście”
Czy można utrzymywać porządek na liście w zamortyzowanym czasie bez użycia operacji arytmetycznych poza ?
ds.data-structures
soft-question
pl.programming-languages
graph-theory
tree
cc.complexity-theory
pcp
co.combinatorics
cg.comp-geom
pr.probability
vc-dimension
cc.complexity-theory
complexity-classes
relativization
soft-question
advice-request
career
soft-question
research-practice
paper-review
journals
co.combinatorics
cc.complexity-theory
complexity-classes
pr.probability
average-case-complexity
cc.complexity-theory
lo.logic
descriptive-complexity
finite-model-theory
ds.algorithms
cc.complexity-theory
approximation-hardness
csp
pcp
cc.complexity-theory
circuit-complexity
jbapple
źródło
źródło
Odpowiedzi:
Tak!
Zobacz także ćwiczenie 8.12 z otwartych struktur danych i Roura „Nowa metoda równoważenia drzew wyszukiwania binarnego” .
źródło