Amortisierte Kosten für das Einfügen / Entfernen auf dem Min-Heap
Ich bin kürzlich auf eine Interviewfrage gestoßen. Es werden keine zusätzlichen Informationen in Frage gestellt (möglicherweise sollte die Standardimplementierung verwendet werden ...)
n beliebige Sequenzen von Einfüge- und Entfernungsoperationen auf einem leeren Min-Heap ( Position für das Löschelement ist bekannt ) haben die folgenden Kosten amortisiert:
A) O (1) einfügen, O entfernen (log n)
B) O (log n) einfügen, O (1) entfernen
Die Option ( B ) ist korrekt.
Ich bin überrascht, wenn ich das Antwortblatt sehe. Ich weiß, dass dies schwierig ist, vielleicht ein leerer Haufen, vielleicht die Position der zu löschenden Elemente zu kennen, ... ich weiß nicht, warum (A) falsch ist? Warum ist (B) wahr?
Antworten
Wenn Sie Operationen in einer Datenstruktur amortisierte Kosten zuweisen, müssen Sie sicherstellen, dass für jede Folge von durchgeführten Operationen die Summe der amortisierten Kosten immer mindestens so groß ist wie die Summe der tatsächlichen Kosten dieser Operationen.
Nehmen wir also Option 1, bei der Einfügungen amortisierte Kosten von O (1) und Löschungen amortisierte Kosten von O (log n) zugewiesen werden. Die Frage, die wir stellen müssen, lautet wie folgt: Stimmt es, dass für jede Folge von Operationen auf einem leeren binären Heap die tatsächlichen Kosten dieser Operationen durch die fortgeführten Anschaffungskosten dieser Operationen begrenzt sind? In diesem Fall lautet die Antwort nein. Stellen Sie sich vor, Sie machen eine Sequenz von nur n Einfügungen in den Heap. Die tatsächlichen Kosten für die Ausführung dieser Operationen können Θ (n log n) betragen, wenn jedes Element bis zum oberen Rand des Heaps sprudeln muss. Die fortgeführten Anschaffungskosten dieser Operationen mit diesem Rechnungslegungsschema wären jedoch O (n), da wir n Operationen durchgeführt haben und so getan haben, als ob jede einzelne O (1) Zeit gekostet hätte. Daher funktioniert dieses amortisierte Rechnungslegungsschema nicht, da wir dadurch die von uns geleistete Arbeit unterschätzen können.
Schauen wir uns andererseits Option 2 an, bei der wir O (log n) als amortisierte Einfügungskosten und O (1) als amortisierte Entfernungskosten zuweisen. Können wir nun eine Folge von n Operationen finden, bei denen die tatsächlichen Kosten dieser Operationen die amortisierten Kosten übersteigen? In diesem Fall lautet die Antwort nein. Hier ist eine Möglichkeit, dies zu sehen. Wir haben die fortgeführten Anschaffungskosten einer Einfügung auf O (log n) festgelegt, was den tatsächlichen Kosten entspricht. Daher können wir die Gesamtsumme nur mit unseren amortisierten Kosten für eine Löschung unterschätzen (O (1)). ), was niedriger ist als die tatsächlichen Kosten einer Löschung. Dies ist hier jedoch kein Problem. Damit wir einen Löschvorgang ausführen können, müssen wir zuvor das zu löschende Element eingefügt haben. Die kombinierten realen Kosten für das Einfügen und Löschen betragen O (log n) + O (log n) = O (log n), und die kombinierten fortgeführten Anschaffungskosten für das Einfügen und Löschen betragen O (log n) + O (1) ) = O (log n). In diesem Sinne ändert das Vorgeben, dass Löschungen schneller sind, nichts an unseren Gesamtkosten.
Eine nette intuitive Möglichkeit, um zu sehen, warum der zweite Ansatz funktioniert, der erste jedoch nicht, besteht darin, darüber nachzudenken, worum es bei der amortisierten Analyse geht. Die Intuition hinter der Amortisation besteht darin, frühere Operationen etwas mehr in Rechnung zu stellen, damit zukünftige Operationen weniger Zeit in Anspruch nehmen. Im Fall des zweiten Abrechnungsschemas ist es genau das, was wir tun: Wir verlagern die Kosten für das Löschen eines Elements aus dem binären Heap wieder auf die Kosten für das Einfügen dieses Elements in den Heap. Auf diese Weise kann die Summe der fortgeführten Kosten nicht niedriger sein als die Summe der tatsächlichen Kosten, da wir die Arbeit nur rückwärts verlagern. Auf der anderen Seite, im ersten Fall sind wir Verschiebung Arbeit vorwärts in der Zeit von Löschungen Lohn für Einfügungen machen. Aber das ist ein Problem, denn wenn wir eine Reihe von Einfügungen vornehmen und dann niemals die entsprechenden Löschungen vornehmen, haben wir die Arbeit auf Operationen verlagert, die nicht existieren.
Da der Heap anfangs leer ist, können Sie nicht mehr Löschungen als Einfügungen ausführen.
Die fortgeführten Anschaffungskosten von O (1) pro Löschung und O (log N) pro Einfügung entsprechen genau den amortisierten Kosten von O (log N) für Einfügungen und Löschungen, da Sie die Löschkosten nur zählen können, wenn Sie dies tun entsprechende Beilage.
Es funktioniert nicht umgekehrt. Da Sie können mehr Einsätze als Löschungen haben, kann es nicht genug Löschungen, die Kosten jeden Einsatz zu zahlen.