Amortisierte Laufzeitanalyse - LinkFang.de





Amortisierte Laufzeitanalyse


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 in mehreren Durchläufen 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, wobei dieser „teure“ Fall aber nur in einem oder wenigen Abläufen des Algorithmus vorkommt und alle anderen Fälle relativ günstig sind. Ziel ist also letztlich, die „durchschnittliche“ obere Schranke im Worst Case zu bestimmen; die obere Schranke, die im ungünstigst denkbaren Durchlauf im Worst Case gilt - und höher liegen kann -, bleibt davon jedoch unberührt.

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

Bei der amortisierten Laufzeitanalyse gibt es prinzipiell drei unterschiedliche Methoden:

Siehe auch

Literatur


Kategorien: Theoretische Informatik

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Amortisierte Laufzeitanalyse (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.