Diskussion:Account-Methode

aus Wikipedia, der freien Enzyklopädie
Letzter Kommentar: vor 5 Jahren von Nomen4Omen in Abschnitt Worst-Case Laufzeit von O(n2) ? — Nein ! O(3×n−3) !
Zur Navigation springen Zur Suche springen

Wofür

[Quelltext bearbeiten]

Wofür verwendet man diese Methode und was sagt sie aus? Gibt es Anwendungsbeispiele? --Manja 20:35, 16. Jan 2005 (CET)

Sollte sich nach der Überarbeitung erledigt haben. --Gms 20:18, 12. Dez. 2009 (CET)Beantworten

Bessere Erläuterung der Theorie

[Quelltext bearbeiten]

Dem Artikel mangelt es etwas an einer abstrakten Erläuterung der Vorgehensweise. Dazu:

Ist das zentrale (durch die Account-Methode belegbare) Argument des dargestellten Beweises, dass sich Setz- und Rücksetzoperationen die Waage halten (müssen)? -- the contented Diskussion 23:40, 9. Feb. 2010 (CET)Beantworten

Begründung für Korrektheit bei Binärzähler fehlt

[Quelltext bearbeiten]

"Da nun bei jeder Inkrementation des Zählers genau ein Bit von 0 auf 1 gesetzt wird, enthält das Konto genug Einheiten um alle möglichen Wechsel von 1 auf 0 zu bezahlen. Also sind die amortisierten Gesamtkosten für n Inkrementation in O(n)."

Warum? - das sollte im Artikel stehn. --mafutrct (Diskussion) 21:58, 1. Nov. 2015 (CET)Beantworten

Worst-Case Laufzeit von O(n2) ? — Nein ! O(3×n−3) !

[Quelltext bearbeiten]

Im Artikel steht seit 23:25, 3. Jun. 2010‎:

"Für das Einfügen von n Elementen in das Array T ergibt sich eine Worst-Case Laufzeit von O(n2) — dies liegt an Zeile 4, die num(T) elementare Einfügeoperationen verursacht."

Wenn ich nachzurechnen versuche, komme ich bei initialem size(T) = 1 auf folgenden Ablauf:

Bedarf
 
size(T)
vorher
num(T)
vorher
num(T)
nachher
size(T)
nachher
Inserts
wiederholt
Insert
neu
Alle
Inserts

Faktor
+1 1 0 1 1 0 1 1 >3×1-3
+1 1 1 2 2 1 1 3 =3×2-3
+1 2 2 3 4 2 1 6 =3×3-3
+1 4 3 4 4 0 1 7 <3×4-3
+1 4 4 5 8 4 1 12 =3×5-3
+1 8 5 6 8 0 1 13 <3×6-3
+1 8 6 7 8 0 1 14 <3×7-3
+1 8 7 8 8 0 1 15 <3×8-3
+1 8 8 9 16 8 1 24 =3×9-3

Das Quadratische kommt bei einer Zeile 3: U := create_table(1 + size(T)).

Dann kommt noch:

"Da wir den Worst-Case betrachten wird angenommen, dass die for each-Schleife bei jedem Aufruf von table_insert durchlaufen wird."

Ja, wie denn das? Wird die Abfrage if num(T) = size(T) einfach ignoriert? Ich verstehe das so, dass nur bei Gleichheit die for each-Schleife ausgeführt wird, also NICHT bei jedem Aufruf von table_insert! --Nomen4Omen (Diskussion) 18:12, 11. Dez. 2018 (CET)Beantworten