Amortisierte Analyse

In der theoretischen Informatik betrachtet die amortisierte Laufzeitanalyse die durchschnittlichen Kosten von Operationen in Folgen. Im Unterschied zur allgemeinen Laufzeitanalyse werden nicht nur die maximalen Kosten der einzelnen Schritte betrachtet, sondern es wird der Worst Case aller Operationen im gesamten Durchlauf des Algorithmus analysiert. Dies kann – beispielsweise bei Fibonacci-Heaps – zu einer besseren oberen Schranke führen, da es häufig Operationen gibt, die zwar teuer sein können, dieser „teure“ Fall aber nur einmal oder wenige Male pro Ablauf des Algorithmus vorkommt und alle anderen Fälle relativ günstig sind.

Bei einer allgemeinen Laufzeitanalyse muss man vom teuersten Fall ausgehen, da dieser nicht insgesamt ausgeschlossen werden darf, aber da der Fall selten vorkommt, ist die damit berechnete Laufzeit schlechter als die tatsächlich anzunehmende.

Bei der amortisierten Laufzeitanalyse gibt es prinzipiell drei unterschiedliche Methoden:

Siehe auch: Komplexitätstheorie, Graphentheorie, Zeitkomplexität, Effizienz, Programmoptimierung

Literatur

  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 17: Amortized Analysis, pp.405–430.

Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Asymptotische Laufzeit — Unter der Zeitkomplexität eines Problems versteht man die Anzahl der Rechenschritte, die ein optimaler Algorithmus zur Lösung dieses Problems benötigt, in Abhängigkeit von der Länge der Eingabe. Man spricht hier auch von der asymptotischen… …   Deutsch Wikipedia

  • Laufzeitkomplexität — Unter der Zeitkomplexität eines Problems versteht man die Anzahl der Rechenschritte, die ein optimaler Algorithmus zur Lösung dieses Problems benötigt, in Abhängigkeit von der Länge der Eingabe. Man spricht hier auch von der asymptotischen… …   Deutsch Wikipedia

  • Worst-Case-Laufzeit — Unter der Zeitkomplexität eines Problems versteht man die Anzahl der Rechenschritte, die ein optimaler Algorithmus zur Lösung dieses Problems benötigt, in Abhängigkeit von der Länge der Eingabe. Man spricht hier auch von der asymptotischen… …   Deutsch Wikipedia

  • Zeitkomplexität — Unter der Zeitkomplexität eines Problems wird in der Datenverarbeitung die Anzahl der Rechenschritte verstanden, die ein optimaler Algorithmus zur Lösung dieses Problems benötigt, in Abhängigkeit von der Länge der Eingabe. Dabei wird hier auch… …   Deutsch Wikipedia

  • Marxistische Wirtschaftstheorie — Die marxistische Wirtschaftstheorie – die politische Ökonomie auf der Grundlage von Das Kapital von Marx – bildet sowohl ihrem Umfang als auch ihrem Inhalt nach den Hauptteil der marxistischen Gesellschaftstheorie (Historischer Materialismus).… …   Deutsch Wikipedia

  • Kritik der Politischen Ökonomie — Die marxistische Wirtschaftstheorie bildet sowohl ihrem Umfang als auch ihrem Inhalt nach den Hauptteil der Marx’schen Theorie. Sie untersucht die ökonomische Funktionsweise der „bürgerlichen“, „kapitalistischen“ Gesellschaft und folgt… …   Deutsch Wikipedia

  • Marxistische Ökonomie — Die marxistische Wirtschaftstheorie bildet sowohl ihrem Umfang als auch ihrem Inhalt nach den Hauptteil der Marx’schen Theorie. Sie untersucht die ökonomische Funktionsweise der „bürgerlichen“, „kapitalistischen“ Gesellschaft und folgt… …   Deutsch Wikipedia

  • Fibonacci-Halde — In der Informatik ist ein Fibonacci Heap (engl. Heap: Halde) eine Datenstruktur, ähnlich zu einem Binomial Heap, die sich als Vorrangwarteschlange einsetzen lässt. Das heißt, dass Elemente mit festgelegter Priorität in beliebiger Reihenfolge… …   Deutsch Wikipedia

  • Fibonacci-Heap — In der Informatik ist ein Fibonacci Heap (englisch heap ‚Halde‘) eine Datenstruktur, ähnlich zu einem Binomial Heap, die sich als Vorrangwarteschlange einsetzen lässt. Das heißt, dass Elemente mit festgelegter Priorität in beliebiger… …   Deutsch Wikipedia

  • Aggregat-Methode — Die Aggregat Methode (auch Aggregationsmethode oder Ganzheitsmethode) ist ein Vorgehen der amortisierten (Laufzeit ) Analyse. Bei der Aggregat Methode wird versucht die durchschnittlichen Kosten einer Einzeloperation zu ermitteln, indem man… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”