Utrzymanie porządku na liście w w Czas

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)$ $AC^0$

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

A C^{0}

$AC^0$

A C^{0}

$AC^0$

A C^{0}

$AC^0$

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