Analisi degli algoritmi

Possiamo progettare diversi algoritmi per risolvere uno stesso problema

Un algoritmo può impiegare molto meno tempo di un altro (MergeSort $nlogn$, QuickSort $n^2$), o usare molto meno spazio di un altro (BubbleSort, SelectionSort, InsertionSort, HeapSort, ..)

Abbiamo bisogno di tecniche di analisi che consentano di valutare un algoritmo solo un base alle sue caratteristiche e non a quelle del codice che lo implementa o della macchina su cui è eseguito

Vogliamo una definizione concreta di efficienza:

• indipendente dal processore
• indipendente dal tipo di istanza
• che dia una misura di come aumenta il tempo di esecuzione al crescere della dimensione dell’input
• indipendente dal modo in cui sarà implementata dal programmatore

Efficienza

<aside> 💡 Forza bruta: per molti problemi non triviali, esiste un naturale algoritmo di forza bruta che controlla ogni potenziale soluzione

</aside>

Tipicamente impiega tempo $2^N$ (o peggio) per input di dimensione $N$

Problemi con l’approccio basato sulla ricerca esaustiva nello spazio di tutte le possibili soluzioni (forza bruta):

• richiede molto tempo
• non fornisce alcuna informazione sulla struttura del problema che vogliamo risolvere

<aside> 💡 Un algoritmo è efficiente se ha una performance migliore, da un punto di vista analitico, dell’algoritmo di forza bruta

</aside>

Algoritmi che hanno performance migliori rispetto agli algoritmi di forza bruta di solito usano euristiche interessanti e forniscono informazioni rilevanti sulla struttura intrinseca del problema e sulla sua trattabilità computazionale

Tempo polinomiale

Proprietà desiderata: quando la dimensione dell’input raddoppia, l’algoritmo dovrebbe risultare più lento solo di un fattore costante $c'$

<aside> 💡 Si dice che un algoritmo impiega tempo polinomiale (poly-time) se quando la dimensione dell’input aumenta di un fattore costante, ad esempio raddoppia, l’algoritmo risulta più lento solo di un fattore costante $c$

</aside>