O(log(n)) wirklich möglich?
Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Verständnis-Frage SkipLists allgemein
Ich glaube ich kapiere gerade nicht ganz, wie eine randomisierte SkipList auf O(log(n)) kommen soll.
Nur um das einmal zu verdeutlichen, was ich mir dabei gedacht habe:
Gehen wir von einer Skip-Liste mit k=3 Ebenen aus, die jeweils eine Länge l von 15 haben, die “Füllung” sieht so aus:
Ebene 2: 1-------------------------------->20------------>25-->29-->32-->45
Ebene 1: 1---------------------->15-->17-->20-->22------->25-->29-->32-->45
Ebene 0: 1-->2-->3-->4-->5-->8-->15-->17-->20-->22-->23-->25-->29-->32-->45Wir suchen jetzt Zahl 4.
Mein überlegter Algorithmus sähe so aus:
Also zuerst nehmen wir den ersten Knoten auf Ebene 2, prüfen ob die Zahl größer ist, ja sie ist größer
→ Nächste Ebene und nächst größerer Knoten (=15) auswählen
→ Schauen ob die gesuchte Zahl kleiner ist
→ Ja sie ist kleiner
→ Den vorherigen Knoten nehmen und eine Ebene absteige bzw. auf.
Damit wären wir auf Ebene 0 und wissen folgendes:
Die gesuchte Zahle ist größer als 1 aber kleiner als 15.
Man muss jetzt also anschließend eine lineare Suche machen, da unsere Knoten nicht als Array existieren, sondern nur Referenzen aufeinander besitzen.
Wenn ich mir das aber so anschaue, kommt man nicht auf O(log(n)), denn O-Kalkül wäre ja in diesem Beispiel:
O(log(n) + n-x), wobei x für die bisherigen Elemente, die bis in die letzte Ebene rausgeschmissen worden sind, steht.
Daraus folgt:
O(log(n) + n-x) = O(n)
Auch mathematisch betrachtet versteh ich nicht wie das gehen soll, denn bei jedem Schritt in der Liste erspare ich mir MAXIMAL l/2 Schritte.
Wenn jetzt gilt:
l<=2^k, dann funktioniert diese Skip-List einwandfrei, aber sobald ich l>2^k habe funktioniert das ganze nicht mehr.
Ich kann damit die Skip-List maximal auf l/2^k Elemente reduzieren, wobei ich am Ende dann wiederum einige wenige Elemente suchen muss und damit käme für O-Kalkül folgendes raus:
O(log(n) + n/(2^k)) = O(n/(2^k)) = O(n)
Denn k ist ja nur ein konstanter Faktor und n/2^32 ist zwar sehr klein aber immer noch nicht gleich log(n).
Jetzt ist die Frage habe ich das total falsch verstanden oder wird in solchen Fällen für O trotzdem log(n) angenommen, da solche Fälle enorm selten passieren?
Ich vermute, dass du k >= log2(l) (also l <= 2^k) wählen musst, um die SkipList sinnvoll zu verwenden.
Aber selbst wenn man das voraussetzt, dann kann es immer noch passieren, dass die Liste so aussieht:
Ebene 2: 1----------------------->15
Ebene 1: 1------------------>8-->15
Ebene 0: 1-->2-->3-->4-->5-->8-->15Wenn ich jetzt die 4 suche, dann habe ich ja wieder ein ähnliches Problem oder nicht?
Die Worst-Case Komplexität ist natürlich O(n). Zum Beispiel auch, wenn jede Spalte nur Ebene 0 erreicht (unwahrscheinlich, aber möglich).
Im Schnitt sollte überwiegen, dass du in jeder der O(log n) Ebenen eine erwartete Schrittanzahl von 2 hast.
Dann ists gut dass ich diese Frage gestellt habe, weil jetzt weiß ich nicht mehr wirklich was das O-Kalkül ausdrückt.
Ich dachte bisher, dass es die obere Grenze für einen Algorithmus ist, egal ob worst case hin oder her.
So gesehen muss ich beim O-Kalkül ja immer den worst case betrachten, weil dieses mir die obere Grenze vorgibt oder nicht?
So ist es. Für Interessierte empfehle ich einen Blick auf das Original-Paper. Dort sind auch genauere Ausführungen zur Laufzeit.
Im Average-Case verhält sich eine Skip-List so wie ein balancierter Baum und kommt so auf den logarithmischen Suchaufwand. Bäume erhalten diese Eigenschaft, indem sie durch Rotationen rebalanciert werden (und haben so bei n Elementen immer eine Höhe von log2(n)). Eine Skip-List kann so etwas natürlich nur dann ähnlich abbilden, wenn genug Ebenen vorhanden sind. Durch den logarithmischen Zusammenhang kommt man aber mit einer relativ kleinen Anzahl an Ebenen schon sehr weit.
[quote=Shadow992]
So gesehen muss ich beim O-Kalkül ja immer den worst case betrachten, weil dieses mir die obere Grenze vorgibt oder nicht?[/quote]
Das wäre bei vielen Algorithmen, die von der Beschaffenheit der Eingabe abhängen (Quicksort!) zu pessimistisch. Pathologische Fälle kann man immer konstruieren. Deshalb gibt man dann meistens einen Worst-Case-Aufwand und den Average-Case an.
Angaben im O-Kalkül drücken für sich allein gestellt zunächst einmal gar nichts aus. O(n) bezeichnet lediglich die Klasse der Funktionen, die (in einem ganz bestimmten Sinne) „langsamer wachsen“ als die Funktion f(n) = n. Es ist grundsätzlich notwendig zu wissen, für welche Größe man sich interessiert. Ob jetzt Speicherbedarf, Laufzeit (worst-case, average-case, best-case), etc., man kann alles exakt angeben („Der Algorithmus führt bei Eingabegröße n genau g(n) = 5n^2 + 3n Instruktionen aus“) oder eben durch Angaben im O-Kalkül vereinfachen („Der Algorithmus führt bei Eingabegröße n O(n^2) Instruktionen aus“).
servus,
kann sich jemand evtl. dazu herablassen mir das mit diesen Listen zu erklären, ich stehe noch vollkommen auf dem schlauch wie das funzen soll und mit den Bäumen wirds noch schlimmer und ich habe ehrlich gesagt keine Lust nochn zweites Übungsblatt voll in den Sand zu setzen… 
greets
mirko
Was hast du verstanden und was nicht? Je spezifischer deine Frage ist, desto eher wirst du eine (hilfreiche) Antwort erhalten.
ja irgendwie alles nicht so richtig… klar das prinzip eines baumes ist mir bewusst, aber wie die umsetzung dann in code auszusehen hat, bzw. wie man buchstaben und zahlen in einem baum verwerten soll, was min/max Höhe sein soll.
Ich vermute mal ich stehe nur ganz feste auf der Leitung…