Diskussion:Account-Methode
Wofür
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)
Bessere Erläuterung der Theorie
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)
Begründung für Korrektheit bei Binärzähler fehlt
"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)
Worst-Case Laufzeit von O(n2) ? — Nein ! O(3×n−3) !
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)
