Einfache ausgewogene Bäume mit O (1) concat?

Im rein funktionalen Worst-Case-Fall haben Brodal et al. rein funktionale ausgeglichene Bäume mit O (1) verketten und O (lg n) einfügen, löschen und finden. Die Datenstruktur ist etwas kompliziert.

Gibt es einen einfacheren ausgeglichenen Suchbaum mit O (1) verkettet, funktional oder nicht?

functional-programming ds.data-structures Apfel
quelle

Antworten:

Sie können trivial eine Datenstruktur mit O (1) amortisierter Verkettungszeit erstellen , indem Sie bei der Verkettung (die O (n log n) kostet) einfach alles von einem Baum auf den anderen einfügen, genau so, wie es beim Erstellen dieses Baums verwendet wurde der erste Platz, also die Gesamtzeit ist immer noch O (n log n)), aber das ist Betrug.

Für den ungünstigsten Fall (O (1)) behaupten die Autoren, es sei ein offenes Problem für jede Datenstruktur gewesen, daher denke ich, dass Sie keine einfache Antwort finden werden.

Alexandre Passos
quelle

Ich bin nicht sicher, ob Brodal et al. bedeutete, dass es ein offenes Problem war, auch in einer kurzlebigen Umgebung. Sprechen Sie von dem abstrakten Satz, der sich auf "ein offenes Problem von Kaplan und Tarjan" bezieht? Wenn dem so ist, denke ich, ist es aus dem Kontext dieses Papiers klar , dass K & T gesagt hat, dass die Frage in einer rein funktionalen Struktur offen war.

Jbapple

Ich habe das Dokument heruntergeladen, aber es heißt eindeutig: "Sie [K & T] haben gefragt, ob die Verknüpfungsoperation auch in einer kurzlebigen Umgebung im schlimmsten Fall in O (1) implementiert werden kann, während Suchen und Aktualisierungen in logarithmischer Zeit unterstützt werden."

Blaisorblade

Guter Punkt, Blaisorblade. Ich habe diesen Satz verpasst.

Jbapple

n

$n$

O (n \log n)

$O(n \log n)$

O (n \log^{2} n)

$O(n \log^2 n)$

Ich habe das von Ihnen erwähnte Papier heruntergeladen und es antwortet mit "Nein", zumindest zum Zeitpunkt der Veröffentlichung des Papiers. Das hat zwei Gründe:

Ein Papier ist erforderlich, um verwandte Arbeiten ordnungsgemäß zu überprüfen, und das tun sie in der Einleitung mit einer Zusammenfassung in Abb. 1, in der "Nein" steht. Zumindest, wenn es in einer seriösen Konferenz veröffentlicht wurde, aber es sieht so aus (Brodal wird in "Purely functional data structures" von C. Okasaki ein paar Mal zitiert, eine Referenz zu diesem Thema).

Sie erwähnen jedoch im Text einen Algorithmus mit der Suchzeit O (log n log log n) und der Verkettung in der Zeit O (1), der in dem K & T-Papier von STOC '96 skizziert ist. Es könnte für Sie interessant sein.
- Die offene Herausforderung von K & T betrifft Wörterbücher mit O (1) Verkettung und O (log N) Suchen / Einfügen / Löschen, auch für kurzlebige Strukturen.

Punkt 1. stellt auch sicher, dass Sie einfach nach Artikeln suchen können, in denen dieser zitiert wird, um spätere Ergebnisse zu erhalten. Diese müssten dann zitiert werden.

Wenn die Frage von praktischer Relevanz wäre (sollte es aber nicht sein), glaube ich, dass konstante Faktoren wichtiger sind als der Unterschied zwischen O (1) und O (log N) (wie in Sedgewicks Einführung in Algorithmen erörtert) Sie müssen nur nach Benchmarks für den Anwendungsfall Ihrer Anwendung suchen.

Blaisorblade
quelle

ESOP ist eine seriöse Konferenz, wenn Sie das gemeint haben.

Charles Stewart

Das war meine Frage, aber für die ESA, in der das Papier veröffentlicht wird, nicht für ESOP (vielleicht hast du das so gemeint). Ich war mir nicht sicher, ob ich mich auf den Konferenzrang verlassen konnte. Diese inoffizielle Rangliste weist darauf hin, dass auch die ESA einen guten

Ruf hat