Data-Format matters

Hi,

Es heißt Suche ist im Average-Case in O(n*log(n)) auf einer unsortiertem Array machbar.
Das Array wird sortiert in O(n*log(n)) Schritten und dann die Suche in O(log(n)) Schritten (Beispiel Binärsuche).
Ist das Array schon sortiert, kann die Suche in O(log(n)) Schritten im Average-Case erfolgen.
Wir sehen: Das Dateiformat ist entscheident.
Weiter ist zu beachten, dass es besser ist die Elemente in einem Binärbaum ab zu speichern als in ein Array, denn: das Einfügen geschieht nicht in O(1), sondern in O(n) Schritten. Sie müssen jedesmal das Array neu kopieren um ein Element einzufügen. Für den Baum hingegen ist es nur notwendig einen neuen Knoten bei den Blättern im Baum einzufügen.
Wir fassen zusammen

                     Baum,        Liste,      Array,       Hashmap
Einfügen:      O(1),         O(1),       O(n),         O(1)
Suchen:         O(log(n)), O(n),       O(log(n)), O(1)

Wir sehen: Ein Array ist keine gute Wahl, weil das Einfügen zu lange dauert. Eine Liste ist nicht gut, weil das suchen zu lange dauert. Besser ist nur der Baum. Und optimal ist die Hashmap. Nur hat die Hashmap nur im Average-Case O(1) für suchen und einfügen. Gelegentlich muss die Hashmap vergrößert werden, das kostet dann O(n). Während das Vergrößern des Baums nur O(1) bedeutet.
Es kann natürlich dazu führen, dass man einen degenerierten Baum bekommt.
Dagegen hilft dann automatisches ausgleichen durch Knotenrotation. Der so genannte "AVL-Baum".
(http://de.wikipedia.org/wiki/AVL-Baum)
Das Ausgleichen des Baums kann im Durchschnitt wieder zuviel kosten. Daher gibt es den Fibonacci-Baum, welcher nicht "ständig" beim Einfügen rotiert.
(http://de.wikipedia.org/wiki/Fibonacci-Baum)

Meine These ist:Setzen wir die Anzahl der Kinder (s) pro Knoten auf s(x_k) = 2^(x_k) mit x_k = Tiefe des Knoten (k) und speichern den Wertebereich der Kinder, statt nur den Wert des Knotens, so bekommen wir für die Suche O(log(log(n))).
Im letzten Schritt muss noch durch die Liste der Kinder hindurch gegangen werden. Dies Liste ist unsotiert und benötigt theoretisch im worst-case O(n) Schritte. Da wir aber den average-case betrachten und sich die neue Tiefe durch log(log(n)) ergibt, sind auch nur log(log(n)) Elemente in der Liste der Kinder.

Verwendet man nun die Ackermannfunktion für s, dann ist ein rotieren nicht mehr notwendig, da die Tiefe praktisch beschränkt ist, da die Ackermannfunktion sehr schnell anwächst und in einer Tiefe von 5 schon alle Atome des Universums enthalten seien können.
Diese Tiefe ist wahrscheinlich zu klein.
Daher empfehle ich besser die Fibonacci-Funktion zu verwenden. Ein rotieren wäre dann wieder notwendig, würde aber deutlich seltener vorkommen.

Es zeigt sich, dass es möglich ist die Komplexität entweder in den Daten oder im Algorithmus darzustellen.

Ich gehe noch einen Schritt weiter und behaupte, dass sich das Travel-Sales-Man Problem in polynomieller Zeit lösen lässt, wenn man entsprechende Datenstrukturen als Grundlage hat.
Dazu ein anderes mal mehr.

Viele Grüße, Seboeh