Was ist die Verkettungskomplexität von symmetrischen Seilen?

ich bei verschiedenen Papieren haben gesucht und hier ist es, die Informationen, die ich gesammelt habe:Was ist die Verkettungskomplexität von symmetrischen Seilen?

SGI implementation und C cords weder Garantie O (1) Zeit Verkettung für lange Seile noch ~ N Tiefe für kürzere log .
Verschiedene Quellen widersprechen sich. Wikipedia Ansprüche O (1) Verkettung. This page sagt, dass die Verkettung nur dann O (1) ist, wenn ein Operand klein und O (log N) anders ist.

Also, was ist die Zeit Komplexität der Verkettung? Wenn genaues Rebalancing durchgeführt wird, um diese Verkettungskomplexität sicherzustellen, während die Baumbalance erhalten bleibt? Werden bestimmte spezifische Nutzungsmuster angenommen, wenn über diese Komplexität gesprochen wird?

Quelle

2010-10-08 ybungalobill

alle Operationen sind 'log (N)' Zeit Komplexität. Rope ist im Wesentlichen ein binärer Suchbaum, der aus impliziten Schlüsseln besteht, die sich in der Natur auf die Größe des Teilbaums beziehen. Dies ermöglicht leistungsstarke Operationen wie concat/split. Eine der möglichen Implementierungen ist die Verwendung einer Treap-Datenstruktur, die absichtlich dazu verwendet wird, mit impliziten Schlüsseln zu arbeiten und mit hoher Wahrscheinlichkeit die Höhe des Baumes mit '4 * log (n) 'Bereich zu halten, was' O (log n) ist. '. Ich habe eine einfache Implementierung mit Treap getan: https://ideone.com/uMt0Mi. – Yerken

@Yerken: Danke, da ich diese Frage gestellt habe, habe ich selbst Seile implementiert - mit garantierter deterministischer 'log N' Komplexität. Es scheint, dass "O (1)" Verkettung ein Missverständnis ist, das von einigen Leuten verbreitet wird, und es in "O (log N)" zu machen ist trivial. Ich habe einen Blick auf Ihren Code geworfen, aber er scheint nicht in Seil-Implementierungen zu passen: Wenn Sie Elternzeiger verwenden, müssen Sie den ganzen Baum klonen (in 'O (N)' time), wenn Sie lokale Änderungen vornehmen. Der Punkt an Seilen ist, dass sie das vermeiden. – ybungalobill

Entschuldigung, verstehe nicht ganz, was meinst du mit dem Klonen eines ganzen Baumes? Alle lokalen Änderungen werden durch Zusammenführen und Teilen vorgenommen, die nur entlang der Schnittlinie erfolgen (wo Zeiger dereferenziert werden), die eine Höhe des Baumes ist. – Yerken

Der Wikipedia-Artikel ist unklar, das Papier "Ropes: an Alternative to Strings", dass es nirgendwo zitiert, behauptet solch eine Komplexität Ergebnis.

Auf der anderen Seite, dieses jüngste Papier (von Gerth Stølting Brodal, Christos Makris und Kostas Tsichlas) tut: "Purely Functional Worst Case Constant Time Catenable Sorted Lists". Sie haben auch O (logn) Suche, also können Sie es zwar "ausgewogen" taggen, ich habe die Details aber nicht gelesen, nur die Ergebnisse.

"Rope" ist ein Begriff, der (relativ) in der Praxis, aber nicht in der Forschung üblich ist. Stattdessen habe ich nach catenable queues (oder Listen) gesucht, vor allem von Leuten wie Tarjan, Okasaki, Kaplan und anderen, von denen ich glaube, dass das Ihre wahre Antwort ist.

Quelle

2010-10-13 16:20:33

Vielen Dank für den Artikel, leider kann er nicht zum Implementieren von Seilen verwendet werden, da er keine effiziente * split * -Operation unterstützt (letzter Absatz des Papiers), sodass wir Teilstrings nicht effizient abrufen können. – ybungalobill

Nun, wenn Sie eine Lösung dafür finden könnten, wäre es veröffentlichbar :) Der Artikel über Seile ist schwer zu folgen, anscheinend hatten die Autoren etwas gegen die Groß-Oh-Notation - aber eine solche Notation würde sehr genau machen, was sie sind nach. Beim Rebalancing sind sie so vage wie es nur geht. "Wir gleichen 'selten' aus." Ok ... hört sich gut an, denke ich ... –

Was ist die Verkettungskomplexität von symmetrischen Seilen?

Antwort

Verwandte Themen