In der Informatik ist amortisierte Analyse eine Methode, Algorithmen zu analysieren, der die komplette Folge von Operationen des Programms denkt. Es berücksichtigt die Errichtung eines Grenzfalls, der für die Leistung eines Algorithmus ohne Rücksicht auf die Eingänge durch das Schauen auf alle Operationen gebunden ist. Am Herzen der Methode ist die Idee, dass, während bestimmte Operationen in Mitteln äußerst kostspielig sein können, sie an einer genug hohen Frequenz nicht vorkommen können, um das komplette Programm niederzudrücken, weil die Zahl von weniger kostspieligen Operationen weit den kostspieligen im langen Lauf zahlenmäßig überlegen sein wird, das Programm über mehrere Wiederholungen "zurückerstattend". Es ist besonders nützlich, weil es Grenzfall-Leistung versichert, anstatt Annahmen über den Staat des Programms zu machen.

Geschichte

Amortisierte Analyse ist am Anfang aus einer Methode genannt gesamte Analyse erschienen, die jetzt durch die amortisierte Analyse untergeordnet wird. Jedoch wurde die Technik zuerst von Robert Tarjan in seiner Zeitung Amortisierte Rechenbetonte Kompliziertheit formell eingeführt, die das Bedürfnis nach einer nützlicheren Form der Analyse gerichtet hat als die allgemeinen probabilistic verwendeten Methoden. Amortisation wurde für sehr spezifische Typen von Algorithmen, besonders diejenigen am Anfang verwendet, die binäre Bäume und Vereinigungsoperationen einschließen. Jedoch ist es jetzt allgegenwärtig und tritt in Spiel ein, wenn man viele andere Algorithmen ebenso analysiert.

Methode

Die Methode verlangt Kenntnisse, von denen Reihen von Operationen möglich sind. Das ist meistens der Fall mit Datenstrukturen, die Staat haben, der zwischen Operationen andauert. Die Grundidee besteht darin, dass eine Grenzfall-Operation den Staat auf solche Art und Weise verändern kann, dass der Grenzfall wieder seit langem nicht vorkommen kann, so seine Kosten "amortisierend".

Es gibt allgemein drei Methoden, um amortisierte Analyse durchzuführen: die gesamte Methode, die Buchhaltungsmethode und die potenzielle Methode. Alle von diesen geben dieselben Antworten, und ihr Gebrauch-Unterschied ist in erster Linie ausführlich und wegen der individuellen Vorliebe.

• Gesamte Analyse beschließt, dass das obere T (n) auf den Gesamtkosten einer Folge von n Operationen gebunden hat, dann die durchschnittlichen Kosten berechnet, um T (n) / n zu sein.
• Die Buchhaltungsmethode bestimmt die individuellen Kosten jeder Operation, seine unmittelbare Ausführungszeit und seinen Einfluss auf die Laufzeit von zukünftigen Operationen verbindend. Gewöhnlich sammeln viele kurz laufende Operationen eine "Schuld" des ungünstigen Staates in der kleinen Zunahme an, während seltene Langzeitoperationen ihn drastisch vermindern.
• Die potenzielle Methode ist der Buchhaltungsmethode ähnlich, aber berechnet Operationen früh zu viel, um ungenügende Ladungen später zu ersetzen.

Beispiele

Als ein einfaches Beispiel, in einer spezifischen Durchführung der dynamischen Reihe, verdoppeln wir die Größe der Reihe jedes Mal, wenn es sich füllt. Wegen dessen kann Reihe-Wiederzuteilung erforderlich sein, und im Grenzfall kann eine Einfügung O (n) verlangen. Jedoch kann eine Folge von n Einfügungen immer in O (n) Zeit getan werden, weil der Rest der Einfügungen in der unveränderlichen Zeit getan wird, so können n Einfügungen in O (n) Zeit vollendet werden. Die amortisierte Zeit pro Operation ist deshalb O (n) / n = O (1).

Eine andere Weise, das zu sehen, ist, an eine Folge von n Operationen zu denken. Es gibt 2 mögliche Operationen: Eine regelmäßige Einfügung, die verlangt, dass eine unveränderliche c Zeit leistet (nehmen c = 1 an), und eine Reihe-Verdoppelung, die O (j) Zeit verlangt (wo j

Beispiel:

Buchhaltungsschema für den Stapel mit der Reihe-Verdoppelung:

- Sagen Sie, dass die Ist-Kosten des Stoßes oder Knalls 1 sind, wenn nicht der Reihe in der Größe anzupassen, und vorkommt

- Die Ist-Kosten des Stoßes sind 1 + nt für einen unveränderlichen t, wenn es Verdoppelung der Reihe-Größe von n bis 2n und das Kopieren n Elemente über die neue Reihe einschließt.

- Also, der Grenzfall wirkliche Zeit für den Stoß ist Θ (n). Jedoch gibt die amortisierte Analyse ein genaueres Bild.

· Die Buchhaltungskosten für einen Stoß, der Reihe-Verdoppelung nicht verlangt, sind 2t,

· Die Buchhaltungskosten für einen Stoß, der Verdoppelung der Reihe von n bis 2n verlangt, sind-nt + 2t,

· Knall ist 0.

Der Koeffizient 2 in den Buchhaltungskosten wird gewählt, um von der Zeit groß genug zu sein, der Stapel wird geschaffen, die Summe der Buchhaltungskosten kann nie negativ sein. Um das informell zu sehen, wenn das Kontogleichgewicht - Nettosumme von Buchhaltungskosten - zu 2nt wächst (kommt Verdoppelung von der Größe n zu 2n vor), dann wird die erste negative Anklage es auf nt + 2t reduzieren. Deshalb ist das ein gültiges Buchhaltungsschema für den Stapel ADT.

· Mit etwas Experimentieren können wir uns überzeugen, dass jeder Koeffizient weniger als 2 zu schließlichem Bankrott im Grenzfall führen werden.

· Amortisierte Kosten = Ist-Kosten + Buchhaltungskosten = 1 + nt + (-nt + 2t) = 1 + 2t.

· Mit diesem Buchhaltungsschema sind die amortisierten Kosten jeder individuellen Stoß-Operation 1 + 2t, ob es Reihe-Verdoppelung oder nicht verursacht und die amortisierten Kosten jeder Knall-Operation 1 sind. So können wir sagen, dass sowohl Stoß als auch im Grenzfall geführter Knall Zeit amortisiert haben, die in Θ (1) ist.

Vergleich zu anderen Methoden

Bemerken Sie, dass Analyse des durchschnittlichen Falls und probabilistic Analyse von probabilistic Algorithmen nicht dasselbe Ding wie amortisierte Analyse sind. In der Analyse des durchschnittlichen Falls zählen wir über alle möglichen Eingänge auf; in der probabilistic Analyse von probabilistic Algorithmen zählen wir über alle möglichen zufälligen Wahlen auf; in der amortisierten Analyse zählen wir über eine Folge von Operationen auf. Amortisierte Analyse nimmt Grenzfall-Eingang an und erlaubt normalerweise zufällige Wahlen nicht.

Eine Analyse des durchschnittlichen Falls für einen Algorithmus ist problematisch, weil der Benutzer von der Tatsache abhängig ist, dass ein gegebener Satz von Eingängen den größten anzunehmenden Unfall nicht auslösen wird. Eine Grenzfall-Analyse hat das Eigentum, häufig eine allzu pessimistische Leistung für einen gegebenen Algorithmus zurückzugeben, wenn die Wahrscheinlichkeit einer Grenzfall-Operation, die mehrmals in einer Folge vorkommt, 0 für bestimmte Programme ist.

Übliche Anwendung

• Im allgemeinen Gebrauch ist ein "amortisierter Algorithmus" derjenige, den eine amortisierte Analyse gezeigt hat, um eine gute Leistung zu bringen.
• Online-Algorithmen verwenden allgemein amortisierte Analyse.