$ \ Phi_1= 1 $ oder $ \ phi_1= 2 $ für den dynamischen $ \ text {table-Insert} $, wobei $ \ phi_i $ die potenzielle Funktion nach $ i $ tiger ist, gemäß CLRs

Question

Folgendes stammt aus Abschnitt Dynamic Tables , Einführung in Algorithmen von cormmen. et. al.

---

In der folgenden Pseudocode gehen wir davon aus, dass $ T $ ein Objekt ist, das den Tisch darstellt. Das Feld $ Tabelle [T] $ enthält einen Zeiger auf den Speicherblock, der den Tisch darstellt. Das Feld $ num [t] $ enthält die Anzahl der Elemente in der Tabelle und das Feld Größe [t] $ ist die Gesamtzahl der Slots in der Tabelle. Zunächst ist die Tabelle leer: $ num [t]= Größe [t]= 0 $ .

$ \ Text {Tischeinsatz (t, x)} $

$ 1 \ Quad \ Text {falls $ Größe [t]= 0 $} $

$ 2 \ QUAD \ QUAD \ Text {Zerweisen Sie dann $ Table [T] $ mit $ 1 $ Slot} $

$ 3 \ Quad \ Quad Size [T] \ Lisplaw 1 $

$ 4 \ QUAD \ Text {if} num [t]= Größe [t] $

$ 5 \ QUAD \ Quad \ Text {Allocate $ NEW {\ \ text {- {{}} Tabelle $ mit $ 2 \ cdot Größe [t] $ Slots} $

$ 6 \ 6 \ Quad \ Quad \ Quad \ Text {Setzen Sie alle Elemente in $ Table [T] $ in $ neue {\ text {-}} Tabelle $} $

$ 7 \ QUAD \ Quad \ Quad \ Text {kostenlose $ Tabelle [T] $} $

$ 8 \ QUAD \ Quad \ Quad Tabelle [T] \ Lisplaw New {\ Text {-}} Tabelle $

$ 9 \ QUAD \ QUAD \ Quad Size [T] \ Lisplaw 2 \ CDOT Größe [T] $

$ 10 \ QUAD \ Text {Einfügen von $ x $ in $ Table [T] $} $

$ 11 \ QUAD NUM [T] \ Lisplaw Num [T] + 1 $

für die amortisierte Analyse für die Folge von $ N $ $ \ Text {Table-Insert} $ Die mögliche Funktion, die sie wählen, ist wie folgt,

$$ \ phi (t)= 2.Num [t] -ssize [t] $$

Analyse der fortgeführten Anschaffungskosten des $ i $ th $ \ Text {Table-Insert} $ Bedienung, wir lassen $ num_i $ die Anzahl der in der Tabelle gespeicherten Elemente hinter dem $ i $ bezeichnen th operation, $ size_i $ Bezeichnen Sie die Gesamtgröße der Tabelle nach dem $ I $ tiger und $ \ phi_i $ Bezeichnen Sie das Potenzial nach dem $ i $ ten Betrieb.

Anfangs haben wir $ num_0= 0, size_0= 0 $ , und $ \ phi_0= 0 $ .

Wenn der $ i $ der Tabelleneinsatzvorgang keine Erweiterung auslöst, haben wir $ size_i= Größe_ {II} $ und $ num_i= num_ {i-1} +1 $ , die fortlaufenden Kosten der Operation sind $ \ widehat {c_i} $ ist die fortgeführten Kosten und $ c_i $ ist die Gesamtkosten.

$$ \ wideHat {c_i}= c_i + \ phi_i- \ phi_ {i-1}= 3 \ text {(Angaben nicht angezeigt)} $$ < / p>

Wenn der $ i $ yoperation eine Erweiterung auslöst, haben wir $ sigrESS_I= 2. size_ {i-1} $ und $ size_ {i-1}= num_ {i-1}= num_i -1 $ , so nochmal, < / p>

$$ \ wideHat {c_i}= c_i + \ phi_i- \ phi_ {i-1}= 3 \ text {(Angaben nicht angezeigt)} $$ < / p>

---

Jetzt ist das Problem, dass sie keine Berechnungen für $ \ wideHat {C_1} $ , die Situation für das erste Einfügen eines Element in der Tabelle (Linie 1,2,3,10,11 des Codes wird nur ausgeführt).

in dieser Situation, die Kosten $ c_1= 1 $ , $ \ phi_0= 0 $ und $ num_1= size_1= 1 \ Impliziert \ phi_1= 2,1-1= 1 $

Wir sehen, dass $ \ phi_1= 1 \ Tag 1 $

so, $$ \ WIDHAT {C_1}= c_1 + \ phi_1- \ phi_0= 2 $$

Der Text sagt jedoch, dass die fortgeführten Anschaffungskosten $ 3 $ sind (ich fühle, dass sie sagen sollen, dass die fortgeführten Anschaffungskosten höchstens $ 3 $ , von dem, was ich verstehen kann)

Außerdem in der darunter liegenden Darstellung

Der Text stellt graphisch dar, der $ \ phi_1= 2 $ , welche Art von Widersprüchen

Er "> $ (1) $ , aber gemäß der Grafik, wenn wir $ \ phi_1= 2 $ annehmen, dann $ \ widehat {c_i}= 3, \ fürall i $

Ich komme nicht ganz dort, wo ich falsch mache.

Answer 1

Sie haben in diesem beliebten Lehrbuch, dessen Namen, dessen Namen wir nicht noch einmal erwähnen dürfen, eine Instanz des berüchtigten Off-of-One-Fehlers erwischt haben.

Um wiederholt zu werden, ist es korrekt, dass "die Kosten $ C_1= 1 $ , $ \ phi_0= 0 $ < / span> "," $ num_1= size_1= 1 $ $ \ impliziert $ $ \ phi_1= 2 \ cdot1-1= 1 $ " und " $ \ Hat {c_1}= $ $ C_1 + \ phi_1- \ phi_0 $ $= 2 $ ". Es ist falsch, diesen $ \ wideHat c_i= 3 $ für alle $ i $ . .

Der erste $ \ Text {T} \ scriptsize {\ Text {lay}} \ Small \ Text {-i} \ skription \ text {nsert} $ Die Bedienung ist in der Tat sehr besonders. Es gilt nicht als Erweiterung, ein Ereignis, das als "in welcher Linien 5-9 ausgeführt werden" definiert wird. Es bleibt jedoch nicht $ size_i= size_ {i-1} $ , entweder. Also ist keine Berechnung für $ \ wideHat {c_i} $ im Lehrbuch fit für $ \ wideHat {c_1} $ .

Dieser Fehler ist verwirrend, da wir dazu neigen, ein beispielhaftes Lehrbuch zu vertrauen, in dem so viel Aufmerksamkeit auf Details und Richtigkeit gezahlt wurden.

Andererseits ist dieser Fehler nicht sehr wichtig, da er, wie Sie dies bemerkt haben, immer noch, dass "die amortisierten Kosten höchstens 3" sind.

Übrigens, wenn Sie den Figur am Ende der Frage näher betrachten, zeigt es das Potenzial am Ende des ersten $ \ Text {t} \ scriptsize { \ text {lay}} \ small \ text {-i} \ scriptsize \ text {nsert} $ operation, $ \ phi_1= 1 $ , die korrekter Wert.