9 : Analisi degli Algoritmi Vers . 2.0 – Aprile 2022
DIMENSIONE DEL PROBLEMA E COMPLESSITA ’ COMPUTAZIONALE
Il numero di operazioni di un algoritmo come abbiamo potuto notare è legato alla dimensione dei dati di input . Quindi possiamo definire il numero di operazioni in funzione della dimensione dei dati di input .
Si usa perciò la notazione generica T ( N ) per indicare la funzione matematica che indica la relazione esistente tra il numero di operazioni di un programma e la dimensione N dei dati in input .
La funzione T ( N ) è chiamata complessità computazionale ( in tempo ) o semplicemente complessità di un algoritmo .
La dimensione N dei dati in input è anche detta dimensione del problema .
Essendo T ( N ) una funzione matematicaè possibile rappresentarla attraverso il suo grafico in un sistema di assi cartesiano ponendo
sull ’ asse delle ascisse o asse x : la dimensione del problema N
sull ’ asse delle ordinate o asse y : la complessità del problema ossia il numero di operazioni T ( N ).
Esempio : Grafici dei costi degli algoritmi Alg _ A e Alg _ B calcolati in precedenza
T ( N )
TAlg _ A ( N )
14
8 7
TAlg _ B ( N )
Esercizi di approfondimento : svolgere gli esercizi contenuti nei seguenti file PDF
Autore : Rio Chierego ( email : riochierego @ libero . it - sito web : www . riochierego . it ) Pag . 6