Sto cercando di capire come eseguire il costo ammortizzato per una tabella dinamica. Supponiamo di utilizzare il metodo di contabilità.
Sia A di dimensione m una matrice di n elementi. Quando n = m, creiamo una nuova matrice di dimensione 4m, quindi copiamo gli elementi di A nel nuovo array. Quando n = m / 4, quindi crei una nuova matrice di dimensione m / 4 e copia gli elementi in quella matrice.
Ciò di cui sono confuso è come calcolare i costi.
Da quello che so finora:
Prima della prima espansione, paghi due dollari per l'inserimento. 1$ per l'inserto e 1$ che hai appena archiviato con l'elemento, in modo che tu possa utilizzarlo successivamente per un'operazione di copia.
Quindi quando lo espandi, usi quello $ memorizzato per spostare l'elemento nel nuovo array.
Ora nel nuovo array gli elementi non avranno alcun $ con essi. Ma ora quando inserisci un nuovo elemento, usi 3$ . 1$ per l'inserto, quindi uno in più per se stesso (per una copia futura) e uno in più per l'elemento precedente appena copiato.
Il problema qui è, e se hai una matrice come questa:
1$ 2$
Quindi inserisci un elemento
1$ 2 3$ _ _ _ _ _
Ora come gestisci un'operazione di cancellazione?