4° Anno TEORIA 1. Complessità computazionale di un algoritmo | Page 13

9 : Analisi degli Algoritmi Vers . 2.0 – Aprile 2022

EFFICIENZA DI UN ALGORITMO

Due algoritmi appartenenti alla stessa classe di complessità ( ossia due algoritmi a parità di complessità computazionale ) possono essere confrontati relativamente al tempo di esecuzione .

Ossia di ciascuno di essi può essere valutata l ’ efficienza .

Si dice che due algoritmi A1 ed A2 con funzioni di complessità rispettivamente pari ad f1 ( N ) ed f2 ( N ) che risolvono lo stesso problema appartengono alla stessa classe di complessità se

In particolare diremo che : - A1 è più efficiente di A2 se :

- A2 è più efficiente di A1 se :

= C con C > 0 costante

= C con C < 1

= C con C > 1

Osservazione importante La complessità computazionale di un algoritmo , come abbiamo visto , è definita come l ’ ordine di grandezza della funzione che determina il numero di operazioni da svolgere per eseguirlo al crescere della dimensione dei dati in input . E ’ in un certo senso una misura di tempo astratta che ha una relazione solo di proporzionalità con il tempo effettivo di esecuzione . Per sapere un dato algoritmo quanto tempo macchina effettivo impiegherà basterà conoscere quanto tempo macchina occorre all ’ elaboratore in questione per eseguire una operazione elementare e moltiplicare poi per il numero complessivo di operazioni stimate .

Autore : Rio Chierego ( email : riochierego @ libero . it - sito web : www . riochierego . it ) Pag . 13