Konstante Abschreibungsdauer

Question

Was ist mit "Constant Amortized Time" gemeint, wenn es um die Zeitkomplexität eines Algorithmus geht?

Answer 1

Amortisierte Zeit in einfachen Worten erklärt:

Wenn man einen Vorgang, sagen wir, eine Million Mal durchführt, interessiert man sich nicht wirklich für den schlechtesten oder den besten Fall dieses Vorgangs - was einen interessiert, ist, wie viel Zeit man insgesamt benötigt, wenn man den Vorgang eine Million Mal wiederholt.

Es macht also nichts aus, wenn der Vorgang einmal sehr langsam ist, solange "einmal" so selten ist, dass die Langsamkeit verwässert wird. Amortisierte Zeit bedeutet im Wesentlichen "durchschnittliche Zeit pro Vorgang, wenn Sie viele Vorgänge durchführen". Die amortisierte Zeit muss nicht konstant sein; man kann eine lineare und eine logarithmische amortisierte Zeit oder etwas anderes haben.

Nehmen wir Mats' Beispiel eines dynamischen Arrays, dem Sie immer wieder neue Elemente hinzufügen. Normalerweise dauert das Hinzufügen eines Elements eine konstante Zeit (d. h., O(1) ). Aber jedes Mal, wenn das Array voll ist, weisen Sie doppelt so viel Platz zu, kopieren Ihre Daten in den neuen Bereich und geben den alten Platz frei. Unter der Annahme, dass Zuweisungen und Freigaben in konstanter Zeit ablaufen, dauert dieser Erweiterungsprozess O(n) Zeit, wobei n die aktuelle Größe des Arrays ist.

Bei jeder Erweiterung benötigen Sie also etwa doppelt so viel Zeit wie bei der letzten Erweiterung. Aber Sie haben auch doppelt so lange gewartet, bevor Sie es getan haben! Die Kosten für jede Erweiterung können also auf die einzelnen Einfügungen "verteilt" werden. Langfristig gesehen bedeutet dies, dass die Gesamtzeit für die Erweiterung m Elemente in das Array ist O(m) und die amortisierte Zeit (d. h. die Zeit pro Einfügung) beträgt somit O(1) .

Answer 2

Das bedeutet, dass das Worst-Case-Szenario im Laufe der Zeit auf O(1) oder konstante Zeit reduziert wird. Ein gängiges Beispiel ist das dynamische Array. Wenn wir bereits Speicher für einen neuen Eintrag zugewiesen haben, wird das Hinzufügen O(1) sein. Wenn wir ihn noch nicht zugewiesen haben, werden wir dies tun, indem wir z. B. das Doppelte der aktuellen Menge zuweisen. Diese spezielle Einfügung wird no O(1) sein, sondern eher etwas anderes.

Wichtig ist, dass der Algorithmus garantiert, dass nach einer Folge von Operationen die teuren Operationen amortisiert werden, so dass die gesamte Operation O(1) wird.

Oder noch strenger ausgedrückt,

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

Answer 3

Um eine intuitive Denkweise darüber zu entwickeln, sollten Sie die Einfügung von Elementen in dynamisches Array (zum Beispiel std::vector in C++). Zeichnen wir ein Diagramm, das die Abhängigkeit von der Anzahl der Operationen (Y) zeigt, die benötigt werden, um N Elemente in ein Array einzufügen:

Die vertikalen Teile des schwarzen Diagramms entsprechen den Neuzuweisungen von Speicherplatz zur Erweiterung eines Arrays. Hier können wir sehen, dass diese Abhängigkeit grob als Linie dargestellt werden kann. Und diese Liniengleichung lautet Y=C*N + b ( C konstant ist, b = 0 in unserem Fall). Daher können wir sagen, dass wir Folgendes ausgeben müssen C*N Operationen im Durchschnitt, um N Elemente zum Array hinzuzufügen, oder C*1 Operationen, um ein Element hinzuzufügen (amortisierte konstante Zeit).

Answer 4

Ich fand die folgende Wikipedia-Erklärung nützlich, nachdem ich sie 3 Mal gelesen hatte:

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

"Dynamisches Array

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

Betrachten Sie ein dynamisches Array, das durch Hinzufügen weiterer Elemente an Größe zunimmt wie z. B. eine ArrayList in Java. Wenn wir mit einem dynamischen Array der Größe 4 beginnen, würde es eine konstante Zeit dauern, vier Elemente hinzuzufügen. Das Hinzufügen eines fünften Elements zu diesem 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. Die nächsten drei Push-Operationen würden in ähnlicher Weise konstante Zeit in Anspruch nehmen, und die anschließende Addition würde eine weitere langsame Verdoppelung der Array-Größe erfordern.

Im Allgemeinen gilt für eine beliebige Anzahl von Schüben n in einem Array der Größe n betrachten, stellen wir fest, dass Push-Operationen konstante Zeit benötigen, außer mit Ausnahme des letzten Vorgangs, der O(n)-Zeit für die Größenverdopplung benötigt Operation. Da es insgesamt n Operationen gab, können wir den Durchschnitt davon nehmen und feststellen, dass das Einschieben von Elementen in das dynamische Array dauert: O(n/n)=O(1), konstante Zeit."

Nach meinem Verständnis eine einfache Geschichte:

Angenommen, Sie haben viel Geld. Und Sie wollen es in einem Raum stapeln. Und du hast lange Hände und Beine, so lang wie du jetzt oder in Zukunft brauchst. Und, Sie müssen alles in einen Raum füllen, so dass es einfach ist, es abzuschließen.

Du gehst also bis zum Ende/Ecke des Raumes und fängst an, sie zu stapeln. Während du sie stapelst, geht dem Raum langsam der Platz aus. Allerdings, wie Sie füllen es war einfach, sie zu stapeln. Du hast das Geld, legst das Geld. Ganz einfach. Es ist O(1). Wir müssen kein vorheriges Geld verschieben.

Sobald der Platz nicht mehr ausreicht. Wir brauchen einen anderen Raum, der größer ist. Hier gibt es ein Problem, da wir nur einen Raum haben können und somit auch nur ein Schloss, müssen wir das gesamte Geld aus diesem Raum in den neuen, größeren Raum verschieben. Wir verschieben also alles Geld aus dem kleinen Raum in den größeren Raum. Das heißt, wir stapeln sie alle wieder. Wir müssen also das gesamte bisherige Geld verschieben. Es ist also O(N). (unter der Annahme, dass N die Gesamtzahl des Geldes des vorherigen Geldes ist)

Mit anderen Worten, bis N war es einfach, nur 1 Operation, aber als wir in einen größeren Raum umziehen mussten, haben wir N Operationen durchgeführt. Mit anderen Worten, wenn wir den Durchschnitt bilden, ist es 1 Einfügung am Anfang und 1 weitere Bewegung beim Umzug in einen anderen Raum. Insgesamt 2 Operationen, eine Einfügung, eine Verschiebung.

Unter der Annahme, dass N groß ist wie 1 Million, selbst in einem kleinen Raum, sind die 2 Operationen im Vergleich zu N (1 Million) nicht wirklich eine vergleichbare Zahl, so dass sie als konstant oder O(1) betrachtet wird.

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 Betrag der Geldmenge im größeren Raum.

Wir haben also N2 (was N von vorher beinhaltet, da wir alle von einem kleinen in einen größeren Raum umziehen)

Wir brauchen nur noch 2 Operationen, eine ist das Einfügen in einen größeren Raum, dann eine weitere Verschiebeoperation, um in einen noch größeren Raum zu gelangen.

Selbst für N2 (1 Milliarde) sind es also 2 Vorgänge für jeden, was wiederum nichts ist. Es ist also konstant, oder O(1)

Wenn der N-Gehalt also von N auf N2 oder sonstwie ansteigt, spielt das keine große Rolle. Es ist immer noch konstant, oder O(1) Operationen für jede der N erforderlich.

---

Nehmen wir an, N ist 1, sehr klein, die Anzahl der Geldstücke ist klein, und Sie haben einen sehr kleinen Raum, in den nur 1 Geldstück passt.

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

Wenn du in den größeren Raum gehst, nimm an, dass dort nur ein weiteres Geld hineinpasst, also insgesamt 2 Geldstücke. Das heißt, das zuvor verschobene Geld und 1 weiteres. Und wieder ist er gefüllt.

Auf diese Weise wächst das N langsam, und es ist nicht mehr konstant O(1), da wir alles Geld aus dem vorherigen Raum verschieben, aber nur 1 weiteres Geld unterbringen können.

Nach 100 Mal passt das neue Zimmer 100 Geldbeträge aus dem vorherigen und 1 Geld mehr, das es aufnehmen kann. Das ist O(N), denn O(N+1) ist O(N), d.h. der Grad von 100 oder 101 ist derselbe, beides sind Hunderte, im Gegensatz zur vorherigen Geschichte von Einsen zu Millionen und Einsen zu Milliarden.

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

---

Ein guter Weg ist also die Zuweisung von mehr Platz, mit Potenzen von 2.

1. Raumgröße = passt in 1 Geldstück
2. Raumgröße = passt für 4 Geldbeträge
3. Raumgröße = 8 Geldstücke passen hinein
4. Raumgröße = 16 Geldstücke passen hinein
5. Raumgröße = passt für 32 Geldstücke
6. Raumgröße = 64 Geldbeträge passen
7. Raumgröße = passt in 128 Geldbeträge
8. Raumgröße = passt in 256 Geldbeträge
9. Raumgröße = passt in 512 Geldbeträge
Größe des 10. Raums = passt in 1024 Geldbeträge
11. Raumgröße= passt 2.048 Geldbeträge
...
16. Raumgröße= passt 65.536 Geldbeträge
...
32. Raumgröße= passt für 4.294.967.296 Geldbeträge
...
64. Raumgröße= passt 18.446.744.073.709.551.616 Geldbeträge

Warum ist das besser? Weil es anfangs langsam zu wachsen scheint und später schneller, d.h. verglichen mit der Speichermenge in unserem RAM.

Das ist hilfreich, denn im ersten Fall ist es zwar gut, aber der Gesamtbetrag der pro Geld zu leistenden Arbeit ist fest (2) und nicht mit der Größe des Raums (N) vergleichbar. Der Raum, den wir in der Anfangsphase genommen haben, könnte zu groß sein (1 Million), den wir möglicherweise nicht vollständig nutzen, je nachdem, ob wir im ersten Fall überhaupt so viel Geld zum Sparen bekommen.

Im letzten Fall, den Potenzen von 2, wächst sie jedoch in den Grenzen unseres Arbeitsspeichers. Wenn also die Anzahl der Potenzen von 2 zunimmt, bleibt die Armotized-Analyse konstant und ist für den begrenzten Arbeitsspeicher, den wir heute haben, geeignet.

Answer 5

Ich habe dieses einfache Python-Skript erstellt, um die amortisierte Komplexität der Anfügeoperation in einer Python-Liste zu demonstrieren. Wir fügen der Liste immer wieder Elemente hinzu und messen die Zeit jedes Vorgangs. Während dieses Prozesses stellen wir fest, dass einige bestimmte Anfügeoperationen viel mehr Zeit benötigen. Diese Spitzen sind auf die neue Speicherzuweisung zurückzuführen, die durchgeführt wird. Wichtig ist, dass die Spitzen mit zunehmender Anzahl von Anfügevorgängen höher werden, aber in größeren Abständen auftreten. Die Zunahme der Abstände ist darauf zurückzuführen, dass jedes Mal, wenn der ursprüngliche Speicher überläuft, ein größerer Speicher (in der Regel das Doppelte des vorherigen) reserviert wird. Ich hoffe, das hilft, ich kann es auf der Grundlage von Vorschlägen weiter verbessern.

import matplotlib.pyplot as plt
import time

a = []
N = 1000000

totalTimeList = [0]*N
timeForThisIterationList = [0]*N
for i in range(1, N):
    startTime = time.time()
    a.append([0]*500) # every iteartion, we append a value(which is a list so that it takes more time)
    timeForThisIterationList[i] = time.time() - startTime
    totalTimeList[i] = totalTimeList[i-1] + timeForThisIterationList[i]
max_1 = max(totalTimeList)
max_2 = max(timeForThisIterationList)

plt.plot(totalTimeList, label='cumulative time')
plt.plot(timeForThisIterationList, label='time taken per append')
plt.legend()
plt.title('List-append time per operation showing amortised linear complexity')
plt.show()

Daraus ergibt sich die folgende Darstellung