$ \ Phi_1= 1 $ o $ \ phi_1= 2 $ per il Dynamic $ \ text {table-insert} $, dove $ \ phi_i $ è la funzione potenziale dopo $ I $ OPERATION, come da CLRS

Question

Il seguente viene dalla sezione Tabelle dinamiche , Introduzione agli algoritmi di Cormen. et. al.

---

.

Nella seguente pseudocodice, assumiamo che $ T $ è un oggetto che rappresenta la tabella. Il campo $ Tabella [T] $ contiene un puntatore al blocco di memoria che rappresenta la tabella. Il campo $ num [T] $ contiene il numero di elementi nella tabella e il campo $ Dimensione [T] $ è il numero totale di slot nella tabella. Inizialmente, la tabella è vuota: $ NUM [T]= Dimensione [T]= 0 $ .

.

$ \ text {table-insert (t, x)} $

$ 1 \ quad \ text {se $ Dimensione [T]= 0 $} $

$ 2 \ quad \ quad \ text {assegna $ tabella [t] $ con $ 1 $ slot} $

$ 3 \ quad \ tain misura [T] \ Levingarrow 1 $

$ 4 \ quad \ text {if} num [t]= dimensione [T] $

$ 5 \ quad \ quad \ text {quindi alloca $ nuovo {\ text {}} tabella $ con $ 2 \ cdot dimensione [T] $ slot} $

$ 6 \ quad \ quad \ quad \ text {inserire tutti gli elementi in $ Tabella [T] $ in $ Nuovo {\ text {}} Tabella $} $

$ 7 \ quad \ quad \ quad \ text {$ $ table [t] $} $

$ 8 \ quad \ quad \ table table [T] \ Levingraw new {\ text {-}} tabella $

$ 9 \ QUAD \ QUAD \ QUAD Dimensione [T] \ LevingAndrow 2 \ Dimensione CDOT [T] $

$ 10 \ quad \ text {inserire $ x $ in $ tabella [t] $} $

$ 11 \ quad num [T] \ Levingarrow num [t] + 1 $

Per l'analisi ammortizzata per la sequenza di una sequenza di $ N $ $ \ text {table-insert} $ La funzione potenziale che scelgono è la seguente,

.

$$ \ phi (t)= 2.num [t] -size [t] $$

per analizzare il costo ammortizzato della $ i $ th $ \ text {table-insert} $ Funzionamento, lasciamo $ NUM_I $ Denna il numero di elementi memorizzati nella tabella dopo la $ I $ Operazione, $ TAGLIO_I $ Denna la dimensione totale della tabella dopo la $ i $ Funzionamento e $ \ PHI_i $ Dennare il potenziale dopo la $ i $ Operazione.

Inizialmente, abbiamo $ num_0= 0, taglia_0= 0 $ e $ .

Se la classe $ i $ L'operazione di insert da tavolo non attiva un'espansione, quindi abbiamo $ Dimensione_I= Dimensione_ {ii} $ e $ num_i= num_ {i-1} +1 $ , il costo ammortizzato dell'operazione è $ \ widehat {c_i} $ è il costo ammortizzato e $ c_i $ è il costo totale.

.

$$ \ widehat {c_i}= c_i + \ phi_i- \ phi_ {i-1}= 3 \ text {(dettagli non mostrati)} $$ < / P >.

Se la classe $ i $ L'operazione attiva un'espansione, quindi abbiamo $ tangent_i= 2. taglia_ {i-1} $ e $ size_ {i-1}= num_ {i-1}= num_i -1 $ , così di nuovo, < / P >.

.

$$ \ widehat {c_i}= c_i + \ phi_i- \ phi_ {i-1}= 3 \ text {(dettagli non mostrati)} $$ < / P >.

---

.

Ora il problema è che non fanno calcoli per $ \ widehat {c_1} $ , la situazione per il primo inserimento di un Elemento nella tabella (linea 1,2,3,10,11 di codice viene eseguito solo).

in quella situazione, il costo $ c_1= 1 $ , $ \ phi_0= 0 $ e $ NUM_1= Dimensione_1= 1 \ IMPLICE \ PHI_1= 2.1-1= 1 $

Vediamo che $ \ phi_1= 1 \ tag 1 $

SO, $$ \ Widehat {c_1}= c_1 + \ phi_1- \ phi_0= 2 $$

Ma il testo dice che il costo ammortizzato è $ 3 $ , (sento che avrebbero dovuto dire che il costo ammortizzato è al massimo $ 3 $ , da quello che posso capire)

Inoltre nella trama sotto,

Il testo rappresenta graficamente la $ \ phi_1= 2 $ quale tipo di contraddice

er "> $ (1) $ , ma come da grafico se assumiamo $ \ phi_1= 2 $ quindi $ \ widehat {c_i}= 3, \ forlt I $

Non vado abbastanza dove sto facendo sbagliando.

Answer 1

Hai catturato un'istanza del famigerato errore off-by-one in quel libro di testo popolare il cui nome non menzioneremo di nuovo.

Per ripetere, è corretto che "il costo $ c_1= 1 $ , $ \ PHI_0= 0 $ < / span> "," $ num_1= size_1= 1 $ $ \ implica $ $ \ phi_1= 2 \ clot1-1= 1 $ " e " $ \ hat {c_1}= $ $ c_1 + \ phi_1- \ phi_0 $ $= 2 $ ". Non è corretto dichiarare che $ \ widehat c_i= 3 $ per tutte le $ I $ . La prima classe $ \ text {t} \ scriptsize {\ text {able}} \ piccolo \ testo {-i} \ scriptsize \ testo {nsert} $ L'operazione è davvero molto speciale. Non è considerato come un'espansione, un evento definito come "in cui vengono eseguite le linee 5-9". Tuttavia, non mantiene $ size_i= size_ {i-1} $ , neanche. Quindi né il calcolo per $-widehat {c_i} $ nel libro di testo è adatto per $ \ widehat {c_1} $ .

L'errore è confuso dato che tendiamo a fidarsi di un libro di testo esemplari in cui tanta attenzione sono stati pagati per i dettagli e la correttezza.

D'altra parte, tale errore non è molto significativo poiché, come hai notato, detiene ancora che "il costo ammortizzato è al massimo 3".

A proposito, se si fa uno sguardo più da vicino alla figura alla fine della domanda, mostra il potenziale alla fine della prima classe $ \ text {t} \ scriptsize { \ testo {able}} \ piccolo \ testo {-i} \ scriptsize \ testo {nsert} $ operazione, $ \ phi_1= 1 $ , il valore corretto