Datenstruktur mit Suchen, Einfügen und Löschen in amortisierter Zeit

Gibt es eine Datenstruktur, um eine geordnete Liste zu führen, die die folgenden Operationen in Amortized Time unterstützt? $O(1)$

GetElement (k) : Liefert das te Element der Liste. $k$
InsertAfter (x, y) : Fügt das neue Element y unmittelbar nach x in die Liste ein.
Löschen (x) : Entfernen Sie x aus der Liste.

Bei den letzten beiden Operationen können Sie davon ausgehen, dass x als Zeiger direkt in die Datenstruktur gegeben ist. InsertElement gibt den entsprechenden Zeiger für y zurück. InsertAfter (NULL, y) fügt y am Anfang der Liste ein.

Ausgehend von einer leeren Datenstruktur aktualisieren beispielsweise die folgenden Vorgänge die geordnete Liste wie folgt:

InsertAfter (NULL, a) [a] $\implies$
InsertAfter (NULL, b) [b, a] $\implies$
InsertAfter (b, c) [b, c, a] $\implies$
InsertAfter (a, d) [b, c, a, d] $\implies$
Löschen (c) [b, a, d] $\implies$

Nach diesen fünf Aktualisierungen sollte GetElement (2) d und GetElement (3) einen Fehler zurückgeben.

data-structures time-complexity asymptotics amortized-analysis BEIM
quelle

In Optimale Algorithmen für Listenindizierung und Subset-Rang (1989) fand ich ein

Lösung für dieses Problem.

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

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

@Raphael: Ich denke, er meint das Element, das

heißen würde, wenn die Datenstruktur ein Array wäre. Arrays unterstützen die erste Operation in

-Zeit, nicht jedoch die zweite. Verknüpfte Listen unterstützen die zweite Operation in

-Zeit, jedoch nicht die erste.

A [k]

$A[k]$

O (1)

$O(1)$

O (1)

$O(1)$

JeffE

Außerdem unterstützen ausgeglichene Binärbäume beide Operationen in der

O (\log n)

$O(\log n)$

JeffE

@ Raffael: Bearbeitet, um zu verdeutlichen.

JeffE

@ JeffE das dynamische Array unterstützt die ersten beiden in

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

O (1)

$O(1)$

Diego

Antworten:

NEIN.

Fredman und Saks haben bewiesen, dass jede Datenstruktur, die diese Operationen unterstützt, mindestens Amortisationszeit pro Operation benötigt $\Omega(\log n/\log\log n)$ . (Dies ist Referenz [1] in dem Artikel von Dietz, den Sie in Ihrem ersten Kommentar erwähnt haben.) Die untere Schranke gilt für das sehr leistungsfähige Zellsondenmodell der Berechnung, bei dem nur die Anzahl der unterschiedlichen Speicheradressen berücksichtigt wird, auf die durch die Aktualisierung und Abfrage zugegriffen wird Algorithmen.

Ohne zusätzliche Annahmen zu den Aktualisierungs- und Abfragevorgängen ist die Datenstruktur von Dietz bestmöglich (zumindest bis zu konstanten Faktoren).

JeffE
quelle

@AT: Diese Bindung wurde nie "als falsch erwiesen". Es gibt Situationen, in denen dies nicht zutrifft, aber das ist eine ganz andere Aussage!

Raphael

@AT: Die untere Grenze der Sortierung wurde in einem viel schwächeren Berechnungsmodell, nämlich binären Entscheidungsbäumen, bewiesen. Die Schranke wurde "als falsch erwiesen", indem schnellere Algorithmen entwickelt wurden, die nicht als binäre Entscheidungsbäume beschrieben werden können. Um zu beweisen, dass die untere Schranke von Fredman und Saks falsch ist, müssen Sie einen schnelleren Algorithmus entwerfen , der nicht auf den Speicher zugreift . Viel Glück.

JeffE

@ JeffE und Raphael; Bitte überprüfen Sie meine andere Antwort und bestätigen / verweigern Sie mein Ergebnis, wenn Sie die Chance bekommen. Vielen Dank.

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

$\Omega(\log n)$

[1] Patrascu, Mihai und Erik D. Demaine. "Logarithmische untere Grenzen im Zell-Sonden-Modell". SIAM J. Comput. 35, nein. 4 (April 2006): 932–963. doi: 10.1137 / S0097539705447256.

BEIM
quelle

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

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

Tatsächlich. Außerdem können Sie bestätigen , dass diese Grenze für die gilt Listendarstellung Problem mit konstanter Größe Worte?

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

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

Ω (\log n)

$\Omega(\log n)$