www.wikidata.de-de.nina.az

Amortisierte Laufzeitanalyse In der theoretischen Informatik betrachtet die amortisierte Laufzeitanalyse die Kosten von

Amortisierte Laufzeitanalyse

In der theoretischen Informatik betrachtet die amortisierte Laufzeitanalyse die Kosten von Operationen in Abfolgen («sequences») dieser Operation. Im Unterschied zur allgemeinen Laufzeitanalyse werden nicht die maximalen Kosten einzelner Schritte betrachtet, sondern es wird die obere Schranke aller Summen der Laufzeiten mehrerer Durchläufe der Operation analysiert und diese Summen durch die Anzahl der Operationen im Durchlauf dividiert, so dass ein Durchschnitt herauskommt, der als Aufwand für die untersuchte Operation genommen wird. Dies kann – beispielsweise bei Fibonacci-Heaps – zu einem besseren Wert führen, da es häufig Operationen gibt, die zwar im Einzelfall teuer sein können, wobei aber ein „teurer“ Fall verglichen mit den anderen (günstigeren) Fällen in einem Ablauf relativ selten vorkommt. Ein anderes Beispiel, dessen Untersuchung 1978 (noch vor der Namensgebung «amortized») stattfand, beschreibt die Anzahl der Rebalancierungsoperationen in BB[α]-Bäumen als amortisiert konstant.

Damit wird die amortisierte Laufzeitanalyse («amortized analysis») als dritte Technik neben die bekannten Laufzeitanalysen der maximalen Kosten («worst-case analysis») und des durchschnittlichen Verhaltens («average-case analysis») gestellt.

Bei der amortisierten Laufzeitanalyse gibt es drei prinzipiell gleichwertige Methoden:

Siehe auch Bearbeiten

Einzelnachweise Bearbeiten

  1. Blum & Mehlhorn
  2. Rebecca Fiebrink

Literatur Bearbeiten

  • Robert Endre Tarjan: Amortized Computational Complexity (= SIAM Journal on Algebraic and Discrete Methods. Band 6, Nr. 2). April 1985, S. 306–318, doi:10.1137/0606031 (duke.edu [PDF]).
  • Norbert Blum, Kurt Mehlhorn: On the Average Number of Rebalancing Operations in Weight-Balanced Trees. 1978 (uni-saarland.de [PDF]): „There is a constant c (depending on α) such that: The total number of rebalancing operations required for executing an arbitrary sequence of n insertions and deletions in an empty BB[α]-tree is bounded by c·n.“
  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms. 2. Auflage. MIT Press, Cambridge MA 2001, ISBN 0-262-03293-7, S. 405–430.
  • Rebecca Fiebrink: Amortized Analysis Explained. 2007 ( [PDF] archiviert am 20 Oktober 2013): „Amortized analysis is a useful tool that complements other techniques such as worst-case and average-case analysis.“
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
In der theoretischen Informatik betrachtet die amortisierte Laufzeitanalyse die Kosten von Operationen in Abfolgen sequences dieser Operation Im Unterschied zur allgemeinen Laufzeitanalyse werden nicht die maximalen Kosten einzelner Schritte betrachtet sondern es wird die obere Schranke aller Summen der Laufzeiten mehrerer Durchlaufe der Operation analysiert und diese Summen durch die Anzahl der Operationen im Durchlauf dividiert so dass ein Durchschnitt herauskommt der als Aufwand fur die untersuchte Operation genommen wird Dies kann beispielsweise bei Fibonacci Heaps zu einem besseren Wert fuhren da es haufig Operationen gibt die zwar im Einzelfall teuer sein konnen wobei aber ein teurer Fall verglichen mit den anderen gunstigeren Fallen in einem Ablauf relativ selten vorkommt Ein anderes Beispiel dessen Untersuchung 1978 noch vor der Namensgebung amortized stattfand beschreibt die Anzahl der Rebalancierungsoperationen in BB a Baumen als amortisiert konstant 1 Damit wird die amortisierte Laufzeitanalyse amortized analysis als dritte Technik neben die bekannten Laufzeitanalysen der maximalen Kosten worst case analysis und des durchschnittlichen Verhaltens average case analysis gestellt 2 Bei der amortisierten Laufzeitanalyse gibt es drei prinzipiell gleichwertige Methoden die Aggregat Methode die Account Methode auch Bankkonto Paradigma genannt die PotentialfunktionmethodeSiehe auch BearbeitenKomplexitatstheorie Graphentheorie Zeitkomplexitat Effizienz ProgrammoptimierungEinzelnachweise Bearbeiten Blum amp Mehlhorn Rebecca FiebrinkLiteratur BearbeitenRobert Endre Tarjan Amortized Computational Complexity SIAM Journal on Algebraic and Discrete Methods Band 6 Nr 2 April 1985 S 306 318 doi 10 1137 0606031 duke edu PDF Norbert Blum Kurt Mehlhorn On the Average Number of Rebalancing Operations in Weight Balanced Trees 1978 uni saarland de PDF There is a constant c depending on a such that The total number of rebalancing operations required for executing an arbitrary sequence of n insertions and deletions in an empty BB a tree is bounded by c n Thomas H Cormen Charles E Leiserson Ronald L Rivest Clifford Stein Introduction to Algorithms 2 Auflage MIT Press Cambridge MA 2001 ISBN 0 262 03293 7 S 405 430 Rebecca Fiebrink Amortized Analysis Explained 2007 archive org PDF archiviert am 20 Oktober 2013 Amortized analysis is a useful tool that complements other techniques such as worst case and average case analysis Abgerufen von https de wikipedia org w index php title Amortisierte Laufzeitanalyse amp oldid 222560144