"ammortizza" significa
reduce or extinguish (a debt) by money regularly put aside.
vale a dire. pagare il debito con un piano di rimborso fisso a rate costanti per un periodo di tempo.
In analisi di algoritmi ammortizzati , "ammortizzare" significa anche ridurre qualcosa da qualcos'altro regolarmente messo da parte?
L'analisi del caso peggiore ammortizzata è chiamata così a causa della sua analogia con la finanza.
L'analisi del caso peggiore ammortizzata esamina più operazioni successive su una struttura dati invece di trattare ogni operazione singolarmente. L'idea è che, a meno che tu non stia sviluppando un sistema in tempo reale, sarai più interessato a come il sistema si comporta in generale rispetto a come si comporta in ogni singolo istante.
Ad esempio, pensa a come implementare un array dinamico (cioè ridimensionabile): indicherai una dimensione adatta per l'array, quindi inizi ad aggiungere elementi uno per uno. A un certo punto, l'array è pieno e quando si aggiunge un nuovo elemento, è necessario creare un nuovo array più grande e copiare tutti gli elementi esistenti nel nuovo array. Questa è un'operazione O (n). Quindi, il caso peggiore per l'aggiunta di un elemento a un array dinamico è O (n). Ciò è chiaramente indesiderabile, un array statico ha O (1) e non vogliamo che i nostri array dinamici siano molto più lenti degli array statici.
Quindi, il caso peggiore è O (n). Ma ... quanto spesso si verifica quel caso peggiore? Bene, se eseguiamo il ridimensionamento giusto , in particolare, se ridimensioniamo in modo esponenziale (ad esempio raddoppiamo le dimensioni ogni volta che l'array è pieno), il ridimensionamento avviene piuttosto raramente.
Intuitivamente, il ridimensionamento deve verificarsi meno di ogni operazione O (n), e richiede O (n) tempo, quindi nel complesso l'array sembra comportarsi come se aveva O (1) aggiungere tempo, anche se non è così. Solo una chiamata che in realtà finisce per innescare il ridimensionamento sarà lenta, tutte le altre saranno veloci, e ci sono molte più chiamate veloci rispetto alle chiamate lente (infatti, ci sono più di O (n) volte più chiamate veloci che chiamate lente ).
Se vuoi che tutti i dettagli cruenti di come esattamente l'analisi del caso peggiore sia definita, come eseguirla e come dimostrare che gli array dinamici hanno O (1) peggiore nel caso peggiore, consulta un manuale di algoritmi .
Ma l'intuizione è questa: proprio come prendere un prestito per comprare una grande macchina si ammortizza nel tempo, perché la macchina più grande significa che fai più soldi che ti permette di ripagare il prestito, assegnando un array più grande e copiando tutto gli elementi over si ammortizzano perché ci sarà un gran numero di "quick added" che ti permetteranno di "ripagare" la penalità di tempo che hai preso su quell'aggiunta lenta. Ecco perché si chiama "analisi ammortizzata", perché ti consente di "prendere in prestito il tempo" per operazioni lente e poco frequenti e di ripagare il tempo con frequenti operazioni veloci.
Si noti che questo è ancora diverso dall'analisi del caso peggiore atteso e dall'analisi del caso medio. Quelli hanno distribuzioni di probabilità e variabili casuali, ma l'analisi del caso peggiore ammortizzata è ancora deterministica nel peggiore dei casi, guarda solo al "quadro più ampio" di come una struttura di dati viene usata nel tempo.
Leggi altre domande sui tag algorithms