Analisi ammortizzata? (Garanzie prestazioni peggiori)

Non implementa analisi ammortizzate. È una tecnica per ottenere limiti di O più precisi.

L'osservazione essenziale che devi fare è che le costose operazioni non possono avvenire in qualsiasi momento.

Nel caso di una struttura dati supportata da array, l'array deve essere ridimensionato di tanto in tanto, quando è pieno. Questa è l'operazione più costosa e richiede O(n) di tempo. Tutti gli altri inserimenti nell'array sono O(1) .

Per determinare il runtime per l'inserimento di n elementi, puoi moltiplicare n con l'operazione più costosa O(n) , che si traduce in un comportamento di runtime complessivo di O(n^2) .

Tuttavia, questo è inaccurato perché il ridimensionamento non può avvenire molto spesso.

Quando parli di soldi, tu ammortizza il costo, quando ripaghi il tuo debito con più piccoli pagamenti nel tempo.

Possiamo usare questo modello per pensare anche agli algoritmi. Semplicemente sostituiamo "tempo" con "denaro" per evitare la mappatura mentale.

Una volta che l'array è pieno alla sua lunghezza n , possiamo raddoppiare la sua dimensione. Dobbiamo effettuare le seguenti operazioni:

• Assegna 2n blocchi di memoria
• copia n elementi

Se assumiamo che sia l'allocazione della memoria che la copia avvengano in tempo lineare, questa sarà un'operazione molto costosa. Tuttavia, ora possiamo usare l'idea del debito e ammortizzarla per la nostra analisi. Solo, stiamo andando ad ammortizzare il nostro debito prima che ce la facciamo davvero.
Supponiamo che il nostro saldo (di soldi / tempo) sia tornato a 0 (cioè non abbiamo un debito e non abbiamo alcun avanzo) una volta che abbiamo ridimensionato l'array.

Questo ha le seguenti implicazioni:

• L'inserimento degli articoli n successivi coprirà il costo del ridimensionamento e della copia (abbiamo n slot utilizzati e n spazi inutilizzati ')

Ora possiamo pensare a quanto ogni operazione di inserimento deve pagare:

• L'inserto
• Il costo di allocare un chunk di memoria
• il costo di spostarlo nella memoria appena allocata

Ora abbiamo coperto i costi per allocare memoria, copiare e inserire gli elementi n successivi. Tuttavia, abbiamo ancora trascurato l'allocazione dello spazio per i vecchi elementi n e la loro copia.

Semplicemente distribuiamo i costi dei nostri vecchi n elementi ai nostri nuovi (ancora da inserire) n elementi:

• Il costo di allocare un chunk di memoria
• il costo di spostarlo nella memoria appena allocata

In totale, ogni operazione di inserimento avrà un costo di 5 unità. Questo paga per il proprio inserimento, e lo spostamento e l'allocazione di spazio per se stesso e uno dei vecchi elementi.

Ogni operazione di inserimento richiede sempre una quantità di tempo costante, ma il ridimensionamento avviene gratuitamente: l'abbiamo ammortizzato spendendo "più" tempo per ogni inserimento.

Come risultato, l'inserimento di n elementi richiede O(n) di tempo.

Altre tecniche per l'analisi ammortizzata sono spiegate qui .

Prima di tutto: è una tecnica per analizzare i runtime del programma, non una tecnica di implementazione per gli algoritmi.

L'esempio menzionato nella tua lista è buono: Aggiunta di un singolo elemento alla struttura dei dati supportata da array. Per ogni singola operazione di aggiunta, nel caso peggiore è necessario copiare tutti gli elementi esistenti. Questo tipo di analisi è troppo pessimista, in quanto non è necessario farlo se si utilizza una strategia di ridimensionamento sensata (moltiplicando la dimensione di alcuni x > 1.0). L'analisi dice quindi che hai un limite O (n ^ 2) - O (n) per elemento di tempo n elementi - mentre il runtime attuale è solo O (n).

Se si calcola il costo di ridimensionamento su tutti gli articoli inseriti (la maggior parte dei quali non ha bisogno di ridimensionamento) si esegue un'analisi ammortizzata. L'analisi ammortizzata produce un limite O (n) che corrisponde al comportamento effettivo dell'algoritmo.