Python - Analisi ammortizzata
L'analisi ammortizzata implica la stima del tempo di esecuzione per la sequenza di operazioni in un programma senza prendere in considerazione l'ampiezza della distribuzione dei dati nei valori di input. Un semplice esempio è che trovare un valore in un elenco ordinato è più veloce che in un elenco non ordinato. Se l'elenco è già ordinato, non importa quanto siano distribuiti i dati. Ma ovviamente la lunghezza dell'elenco ha un impatto in quanto decide il numero di passaggi che l'algoritmo deve compiere per ottenere il risultato finale.
Quindi vediamo che se il costo iniziale di un singolo passaggio per ottenere un elenco ordinato è elevato, il costo dei passaggi successivi per trovare un elemento diventa considerevolmente basso. Quindi l'analisi ammortizzata ci aiuta a trovare un limite al tempo di esecuzione nel caso peggiore per una sequenza di operazioni. Esistono tre approcci all'analisi ammortizzata.
Accounting Method- Ciò comporta l'assegnazione di un costo a ciascuna operazione eseguita. Se l'operazione effettiva termina più rapidamente del tempo assegnato, nell'analisi viene accumulato un credito positivo. Nello scenario inverso sarà un credito negativo. Per tenere traccia di questi crediti accumulati, utilizziamo uno stack o una struttura ad albero dei dati. Le operazioni che vengono eseguite in anticipo (come lo smistamento della lista) hanno un costo ammortizzato elevato ma le operazioni che sono in ritardo nella sequenza hanno un costo ammortizzato inferiore in quanto viene utilizzato il credito accumulato. Quindi il costo ammortizzato è un limite superiore del costo effettivo.
Potential Method- In questo metodo il credito risparmiato viene utilizzato per operazioni future come funzione matematica dello stato della struttura dati. La valutazione della funzione matematica e il costo ammortizzato dovrebbero essere uguali. Quindi, quando il costo effettivo è maggiore del costo ammortizzato, si verifica una diminuzione del potenziale e viene utilizzato per operazioni future costose.
Aggregate analysis - In questo metodo stimiamo il limite superiore sul costo totale di n passi. Il costo ammortizzato è una semplice divisione del costo totale e del numero di passaggi (n) ..