DAA - Analisi degli algoritmi
Nell'analisi teorica degli algoritmi, è comune stimare la loro complessità in senso asintotico, cioè stimare la funzione di complessità per input arbitrariamente grandi. Il termine"analysis of algorithms" è stato coniato da Donald Knuth.
L'analisi degli algoritmi è una parte importante della teoria della complessità computazionale, che fornisce una stima teorica per le risorse richieste da un algoritmo per risolvere uno specifico problema computazionale. La maggior parte degli algoritmi sono progettati per funzionare con input di lunghezza arbitraria. L'analisi degli algoritmi è la determinazione della quantità di risorse di tempo e spazio necessarie per eseguirla.
Di solito, l'efficienza o il tempo di esecuzione di un algoritmo è indicato come una funzione che collega la lunghezza dell'ingresso al numero di passi, nota come time complexityo volume di memoria, noto come space complexity.
Il bisogno di analisi
In questo capitolo, discuteremo la necessità di analisi degli algoritmi e come scegliere un algoritmo migliore per un particolare problema poiché un problema computazionale può essere risolto da algoritmi differenti.
Considerando un algoritmo per un problema specifico, possiamo iniziare a sviluppare il riconoscimento di modelli in modo che tipi di problemi simili possano essere risolti con l'aiuto di questo algoritmo.
Gli algoritmi sono spesso abbastanza diversi tra loro, sebbene l'obiettivo di questi algoritmi sia lo stesso. Ad esempio, sappiamo che un insieme di numeri può essere ordinato utilizzando diversi algoritmi. Il numero di confronti eseguiti da un algoritmo può variare con altri per lo stesso input. Quindi, la complessità temporale di questi algoritmi può differire. Allo stesso tempo, dobbiamo calcolare lo spazio di memoria richiesto da ogni algoritmo.
L'analisi dell'algoritmo è il processo di analisi della capacità di risoluzione dei problemi dell'algoritmo in termini di tempo e dimensione richiesti (la dimensione della memoria per l'archiviazione durante l'implementazione). Tuttavia, la preoccupazione principale dell'analisi degli algoritmi è il tempo o le prestazioni richiesti. In generale, eseguiamo i seguenti tipi di analisi:
Worst-case - Il numero massimo di passaggi eseguiti su qualsiasi istanza di dimensione a.
Best-case - Il numero minimo di passaggi eseguiti su qualsiasi istanza di dimensione a.
Average case - Un numero medio di passaggi eseguiti su qualsiasi istanza di dimensione a.
Amortized - Una sequenza di operazioni applicate all'input della dimensione a media nel tempo.
Per risolvere un problema, dobbiamo considerare il tempo e la complessità dello spazio poiché il programma può essere eseguito su un sistema in cui la memoria è limitata ma è disponibile uno spazio adeguato o può essere viceversa. In questo contesto, se confrontiamobubble sort e merge sort. L'ordinamento a bolle non richiede memoria aggiuntiva, ma l'ordinamento di unione richiede spazio aggiuntivo. Sebbene la complessità temporale del Bubble Sort sia maggiore rispetto al Merge Sort, potrebbe essere necessario applicare il Bubble Sort se il programma deve essere eseguito in un ambiente in cui la memoria è molto limitata.