9 : Analisi degli Algoritmi Vers . 2.0 – Aprile 2022
ORDINE DI GRANDEZZA
Confrontando 2 algoritmi può accadere che il primo esegua meno operazioni dell ’ altro quando la dimensione del problema è bassa , ma le cose si ribaltino quando la dimensione cresce .
Quindi conviene fare riferimento all ’ ordine di grandezza delle complessità ossia valutare la complessità per valori molto grandi delle dimensioni del problema .
Si parla in questo caso di complessità asintotica e si esprime in notazione matematica nel seguente modo lim T ( N )
N� ∞
In altre parole si ottiene una espressione in funzione di N che indica qual è il comportamento all ’ infinito ( asintotico ) dell ’ algoritmo .
Introduciamo le seguenti definizioni :
Siano f ( N ) e g ( N ) due funzioni . Si dice che f ( N ) è di ordine di grandezza g ( N ) e si scrive O ( g ( N )) e si legge “ O grande di g di N ” se esiste una costante C > 0 tale che per tutti i valori N > 0 accade che f ( N ) < C * g ( N )
Pertanto dire che f ( N ) è O ( g ( N )) significa dire che g ( N ) è un limite superiore alla crescita di f ( N ) ossia che f ( N ) non cresce più di g ( N ) ed il suo grafico da un certo punto in poi sarà sotto al grafico di g ( N ).
T ( N ): numero di operazioni
C * g ( N ) f ( N )
Si dice che f ( N ) è proporzionale a g ( N ) ossia che f ( N ) e g ( N ) sono dello stesso ordine di grandezza se f ( N ) è O ( g ( N )) e g ( N ) è O ( f ( N ))
Sarà quindi possibile fare affermazioni del tipo “ la complessità computazionale T ( N ) per questo algoritmo è proporzionale ad N 2 ” , lasciando non specificata la costante C di proporzionalità .
Autore : Rio Chierego ( email : riochierego @ libero . it - sito web : www . riochierego . it ) Pag . 10