Quando dobbiamo risolvere un problema e, quando molti modi sono disponibili per risolvere il problema (ad esempio Matrice catena di moltiplicazione problema), a quel tempo, l’analisi dell’algoritmo è necessario.

Analisi di algoritmi significa stimare la loro complessità in senso asintotico. Il termine “analisi degli algoritmi” è stato coniato da Donald Knuth. L’analisi degli algoritmi è la determinazione della quantità di risorse temporali e spaziali necessarie per eseguirla.

La maggior parte degli algoritmi sono di natura ricorsiva, usano la strategia divide et impera. L’algoritmo ricorsivo si chiama per gli altri input. Questo di solito fa parte dell’input originale ma ha una dimensione più piccola (sotto-problema). Ci sono molti modi per risolvere la relazione di ricorrenza. Sono i seguenti:

1. Teorema maestro

2. Metodo dell’albero di ricorrenza

3. Metodo di sostituzione

4. Cambio di metodo variabile

Tra tutti questi metodi il teorema principale è il metodo più veloce per trovare la complessità temporale della funzione. È molto facile da capire e facile da applicare. Dobbiamo solo ricordare alcuni casi. Quindi ci siamo.