webentwicklung-frage-antwort-db.com.de

Konstante Amortisationszeit

Was ist unter "Constant Amortized Time" zu verstehen, wenn es um die zeitliche Komplexität eines Algorithmus geht?

385
VarunGupta

Amortisierte Zeit in einfachen Worten erklärt:

Wenn Sie eine Operation millionenfach durchführen, interessiert Sie der schlechteste oder der beste Fall dieser Operation nicht wirklich - es ist Ihnen wichtig, wie viel Zeit insgesamt in Anspruch genommen wird, wenn Sie die Operation millionenfach wiederholen .

Es spielt also keine Rolle, ob die Operation ab und zu sehr langsam ist, solange "ab und zu" selten genug ist, um die Langsamkeit aufzulösen. Im Wesentlichen amortisierte Zeit bedeutet "durchschnittliche Zeit, die pro Operation benötigt wird, wenn Sie viele Operationen ausführen". Amortisierte Zeit muss nicht konstant sein; Sie können linear und logarithmisch amortisierte Zeit haben oder was auch immer.

Nehmen wir das Beispiel einer Matte für ein dynamisches Array, zu dem Sie wiederholt neue Elemente hinzufügen. Normalerweise dauert das Hinzufügen eines Elements eine konstante Zeit (d. H. O(1)). Jedes Mal, wenn das Array voll ist, weisen Sie doppelt so viel Speicherplatz zu, kopieren Ihre Daten in die neue Region und geben den alten Speicherplatz frei. Unter der Annahme, dass Zuweisungen und Freigaben in konstanter Zeit ausgeführt werden, benötigt dieser Vergrößerungsprozess O(n) Zeit, wobei n die aktuelle Größe des Arrays ist.

Jedes Mal, wenn Sie vergrößern, benötigen Sie ungefähr doppelt so viel Zeit wie beim letzten Vergrößern. Aber Sie haben auch doppelt so lange gewartet, bevor Sie es tun! Die Kosten für jede Erweiterung können somit auf die Einfügungen "verteilt" werden. Dies bedeutet, dass auf lange Sicht die Gesamtzeit für das Hinzufügen von m Elementen zum Array O(m) ist und die amortisierte Zeit (dh Zeit pro Einfügung) O(1).

734
Artelius

Dies bedeutet, dass im schlimmsten Fall im Laufe der Zeit standardmäßig O (1) oder eine konstante Zeit verwendet wird. Ein häufiges Beispiel ist das dynamische Array. Wenn wir bereits Speicher für einen neuen Eintrag reserviert haben, ist das Hinzufügen von O (1). Wenn wir es nicht zugewiesen haben, werden wir dies tun, indem wir beispielsweise den doppelten aktuellen Betrag zuweisen. Diese bestimmte Einfügung ist nicht O (1), sondern etwas anderes.

Wichtig ist, dass der Algorithmus garantiert, dass nach einer Abfolge von Operationen die teuren Operationen amortisiert werden und dadurch die gesamte Operation O (1) ausgeführt wird.

Oder genauer gesagt,

Es gibt eine Konstante c, so dass für jede Abfolge von Operationen (auch eine, die mit einer kostspieligen Operation endet) der Länge L die Zeit nicht größer als ist c * L (Danke Rafał Dowgird )

55

Um eine intuitive Denkweise zu entwickeln, ziehen Sie die Einfügung von Elementen in dynamisches Array in Betracht (zum Beispiel std::vector in C++). Lassen Sie uns ein Diagramm zeichnen, das die Abhängigkeit der Anzahl der Operationen (Y) zeigt, die zum Einfügen von N Elementen in ein Array erforderlich sind:

plot

Vertikale Teile des schwarzen Graphen entsprechen Neuzuordnungen des Speichers, um ein Array zu erweitern. Hier sehen wir, dass diese Abhängigkeit grob als Linie dargestellt werden kann. Und diese Geradengleichung ist Y=C*N + b (C ist konstant, b = 0 in unserem Fall). Daher können wir sagen, dass wir C*N Operationen im Durchschnitt, um N Elemente zum Array hinzuzufügen, oder C*1 Operationen zum Hinzufügen eines Elements (amortisierte konstante Zeit).

18
Megamozg

Ich fand die folgende Wikipedia-Erklärung nützlich, nachdem ich dreimal wiederholt gelesen hatte:

Quelle: https://en.wikipedia.org/wiki/Amortized_analysis#Dynamic_Array

"Dynamisches Array

Amortisierte Analyse der Push-Operation für ein dynamisches Array

Stellen Sie sich ein dynamisches Array vor, dessen Größe zunimmt, wenn ihm weitere Elemente hinzugefügt werden, z. B. eine ArrayList in Java. Wenn wir mit einem dynamischen Array der Größe 4 beginnen würden, würde es eine konstante Zeit dauern, bis vier Elemente darauf platziert sind. Das Verschieben eines fünften Elements auf dieses Array würde jedoch länger dauern, da das Array ein neues Array mit der doppelten aktuellen Größe (8) erstellen müsste, die alten Elemente in das neue Array kopieren und dann das neue Element hinzufügen müsste. Die nächsten drei Push-Operationen würden ebenfalls eine konstante Zeit in Anspruch nehmen, und dann würde das anschließende Hinzufügen eine weitere langsame Verdoppelung der Array-Größe erfordern.

Wenn wir eine beliebige Anzahl von Push-Vorgängen n in ein Array der Größe n einbeziehen, stellen wir im Allgemeinen fest, dass Push-Vorgänge eine konstante Zeit benötigen, mit Ausnahme des letzten Vorgangs, der O(n) Zeit benötigt, um die Größenverdopplungsoperation auszuführen. Da es insgesamt n Operationen gab, können wir den Durchschnitt dieser Operationen nehmen und feststellen, dass für das Verschieben von Elementen auf das dynamische Array Folgendes erforderlich ist: O (n/n) = O (1), konstante Zeit.

Nach meinem Verständnis als einfache Geschichte:

Angenommen, Sie haben viel Geld. Und Sie möchten sie in einem Raum stapeln. Und Sie haben lange Hände und Beine, so lange Sie jetzt oder in Zukunft brauchen. Und Sie müssen alles in einem Raum ausfüllen, damit es einfach ist, ihn zu verschließen.

Sie gehen also bis zum Ende/der Ecke des Raums und beginnen, sie zu stapeln. Während Sie sie stapeln, geht dem Raum langsam der Raum aus. Beim Befüllen war es jedoch einfach, sie zu stapeln. Hab das Geld, leg das Geld. Einfach. Es ist O (1). Wir müssen kein vorheriges Geld bewegen.

Sobald der Platz knapp wird. Wir brauchen einen anderen Raum, der größer ist. Hier gibt es ein Problem, da wir nur 1 Raum haben können, so dass wir nur 1 Schloss haben können, müssen wir das gesamte in diesem Raum vorhandene Geld in den neuen größeren Raum verschieben. Verschieben Sie also alles Geld von einem kleinen Raum in einen größeren Raum. Das heißt, stapeln Sie alle erneut. Wir müssen also das gesamte bisherige Geld bewegen. Es ist also O (N). (Angenommen, N ist die Gesamtzahl des Geldes des vorherigen Geldes.)

Mit anderen Worten, es war einfach bis N, nur 1 Operation, aber wenn wir in einen größeren Raum umziehen müssen, haben wir N Operationen durchgeführt. Mit anderen Worten, wenn wir einen Durchschnitt bilden, ist es 1 Einfügung am Anfang und 1 weitere Bewegung, während wir in einen anderen Raum ziehen. Insgesamt 2 Operationen, ein Einsatz, ein Zug.

Angenommen, N ist selbst in einem kleinen Raum groß wie 1 Million, dann sind die beiden Operationen im Vergleich zu N (1 Million) keine wirklich vergleichbare Zahl, so dass sie als konstant oder O (1) betrachtet werden.

Angenommen, wir machen das alles in einem anderen größeren Raum und müssen wieder umziehen. Es ist immer noch dasselbe. sagen wir, N2 (sagen wir 1 Milliarde) ist der neue Geldbetrag in dem größeren Raum

Wir haben also N2 (einschließlich N der vorherigen, da wir alle von kleinen zu größeren Räumen wechseln)

Wir brauchen nur noch 2 Operationen, eine wird in einen größeren Raum eingefügt, dann eine weitere Verschiebeoperation, um in einen noch größeren Raum zu gelangen.

Selbst für N2 (1 Milliarde) sind es also 2 Operationen für jede. das ist wieder nichts. Also ist es konstant, oder O (1)

Wenn also N von N auf N2 steigt, spielt es keine große Rolle. Es ist immer noch konstant oder es sind O(1) Operationen für jedes der N erforderlich.


Angenommen, Sie haben N als 1, sehr klein, der Geldbetrag ist klein, und Sie haben einen sehr kleinen Raum, in den nur 1 Geldbetrag passt.

Sobald Sie das Geld in den Raum füllen, ist der Raum gefüllt.

Wenn Sie in den größeren Raum gehen, nehmen Sie an, dass nur noch ein Geld in den Raum passen kann, also insgesamt 2 Geldbeträge. Das heißt, das bisherige bewegte Geld und 1 weiteres. Und wieder ist es gefüllt.

Auf diese Weise wächst das N langsam, und es ist kein konstantes O (1) mehr, da wir das gesamte Geld aus dem vorherigen Raum bewegen, sondern nur noch 1 weiteres Geld aufnehmen können.

Nach 100-mal passt der neue Raum zu 100 Geldbeträgen aus dem vorherigen und 1 weiteren Geldbetrag, den er aufnehmen kann. Dies ist O (N), da O (N + 1) O (N) ist, das heißt, der Grad von 100 oder 101 ist derselbe, beide sind Hunderte, im Gegensatz zur vorherigen Geschichte von Einsen zu Millionen und Einsen zu Milliarden .

Dies ist also eine ineffiziente Methode, um Räume (oder Speicher/RAM) für unser Geld (Variablen) zuzuweisen.


Ein guter Weg ist also, mehr Raum mit Zweierpotenzen zuzuweisen.

1. Raumgröße = passt zu 1 Geldbetrag
2. Raumgröße = passt zu 4 Geldbeträgen
3. Raumgröße = passt zu 8 Geldbeträgen
4. Raumgröße = passt 16 Geld
5. Raumgröße = passt für 32 Geldpunkte
6. Raumgröße = passt für 64 Geldpunkte
7. Raumgröße = passt 128 Geld
8. Raumgröße = passt zu 256 Geldbeträgen
9. Raumgröße = 512 Geldbeträge
10. Raumgröße = passt zu 1024 Geldbeträgen
11. Raumgröße = passt für 2.048 Geldpunkte
...
16. Raumgröße = passt zu 65.536 Geldbeträgen
...
32. Raumgröße = passt zu 4.294.967.296 Geldbeträgen
...
64. Raumgröße = passt zu 18.446.744.073.709.551.616 Geldbeträgen

Warum ist das besser? Weil es anfangs langsam und später schneller zu wachsen scheint, verglichen mit der Größe des Arbeitsspeichers in unserem RAM.

Dies ist hilfreich, da im ersten Fall, obwohl es gut ist, die pro Geld zu erledigende Gesamtarbeitsmenge fest ist (2) und nicht mit der Raumgröße (N) vergleichbar ist, möglicherweise auch der Raum, den wir in der Anfangsphase in Anspruch genommen haben groß (1 Million), die wir möglicherweise nicht vollständig nutzen, abhängig davon, ob wir im ersten Fall so viel Geld zum Sparen haben.

Im letzten Fall jedoch, Potenzen von 2, wächst es in den Grenzen unseres RAM. Wenn also die Potenzen um 2 erhöht werden, bleibt sowohl die Armotized-Analyse konstant als auch die begrenzte RAM, die wir derzeit haben.

12

Die obigen Erläuterungen beziehen sich auf die Aggregatanalyse, bei der ein "Durchschnitt" über mehrere Operationen ermittelt werden soll. Ich bin nicht sicher, wie sie auf die Banker-Methode oder die Physiker-Methoden der amortisierten Analyse zutreffen.

Jetzt. Ich bin mir der richtigen Antwort nicht ganz sicher. Es hätte aber mit der Grundbedingung der beiden Methoden Physiker + Banker zu tun:

(Summe der fortgeführten Betriebskosten)> = (Summe der tatsächlichen Betriebskosten).

Die Hauptschwierigkeit, mit der ich konfrontiert bin, besteht darin, dass ich angesichts der Tatsache, dass die amortisierten asymptotischen Betriebskosten von den normalen asymptotischen Kosten abweichen, nicht sicher bin, wie ich die Bedeutung der amortisierten Kosten einschätzen soll.

Wenn jemand meine fortgeführten Anschaffungskosten angibt, weiß ich, dass dies nicht dasselbe ist wie die normalen asymptotischen Kosten. Welche Schlussfolgerungen kann ich dann aus den fortgeführten Anschaffungskosten ziehen?

Da wir den Fall haben, dass einige Vorgänge überladen sind, während andere Vorgänge unterladen sind, könnte eine Hypothese lauten, dass die Angabe der fortgeführten Anschaffungskosten einzelner Vorgänge bedeutungslos wäre.

Zum Beispiel: Für einen Fibonacci-Heap ist es bedeutungslos, die fortgeführten Anschaffungskosten von nur einem Abnahmeschlüssel als O(1) zu bezeichnen, da die Kosten durch "Arbeiten früherer Operationen zur Erhöhung des Potentials des Heaps" reduziert werden . "

OR

Wir könnten eine andere Hypothese haben, die folgende Gründe für die fortgeführten Anschaffungskosten hat:

  1. Ich weiß, dass der teuren Operation MULTIPLE LOW-COST-Operationen vorausgehen werden.

  2. Aus Gründen der Analyse werde ich einige kostengünstige Vorgänge überladen, so dass sich ihre ASYMPTOTIC-Kosten nicht ändern.

  3. Mit diesen erhöhten Kosteneinsparungen kann ich NACHWEISEN, dass ein teurer Betrieb geringere ASYMPTOTISCHE KOSTEN verursacht.

  4. Somit habe ich den ASYMPTOTIC-BOUND der Kosten von n Operationen verbessert/gesenkt.

Die Amortized-Cost-Analyse + Amortized-Cost-Bounds gelten nun nur für die teuren Operationen. Die billigen Operationen haben die gleichen asymptotischen Amortisationskosten wie ihre normalen asymptotischen Kosten.

1
Misraji