9 : Analisi degli Algoritmi Vers . 2.0 – Aprile 2022
ANALISI AL CASO OTTIMO , PESSIMO E MEDIO Il termine complessità qui introdotto risulta ancora molto generico ed impreciso . E ’ importante infatti valutare la sequenza di dati che si presentano in input ed i loro specifici valori .
La complessità di un algoritmo pertanto è legata ai valori dati in input ed a come i dati sono disposti oltre che alla loro dimensione .
In definitiva , per valutare le prestazioni di un algoritmo , non essendo possibile un calcolo esatto , si esegue una stima sulla base del caso migliore e del caso peggiore , indicando ove possibile anche il caso medio .
Quindi in generale si prevedono tre tipi di analisi ossia : a ) analisi al caso ottimo ; b ) analisi al caso pessimo ; c ) analisi al caso medio .
Quindi la funzione complessità T ( N ) va SEMPRE analizzata nel caso più favorevole , in quello sfavorevole e nel caso medio in base alla dimensione ed alla disposizione dei dati in ingresso .
Per esprimere tali funzioni di complessità utilizzeremo le seguenti notazioni : a ) Tottimo ( N ); b ) Tpessimo ( N ); c ) Tmedio ( N ).
Per decidere quale considerare delle tre , va analizzato il tipo di applicazione , ma in genere è la funzione T medio ( N ) quella che riveste la maggiore importanza . Se risultasse difficile da individuare ci si riferirà alla funzione T pessimo ( N ).
Ricerca di un elemento in un insieme ordinato di elementi
( per esempio un numero telefonico in un elenco ordinato alfabeticamente o un numero intero in un insieme ordinato di numeri interi )
FUNZIONE Ric _ Seq ( VAL v ARRRAY [ ] DI INT , VAL dim : INT , VAL x : INT ): BOOL trovato : BOOL i : INT
MENTRE ( i ≤ dim ) AND ( NOT trovato ) ESEGUI SE ( v [ i ] = x )
ALLORA trovato � VERO FINE SE i � i + 1 FINE MENTRE
FUNZIONE Ric _ Bin ( VAL v ARRRAY [ ] DI INT , VAL dim : INT , VAL x : INT ): BOOL trovato : BOOL primo , ultimo , centro : INT
MENTRE ( primo ≤ ultimo ) AND ( NOT trovato ) ESEGUI centro � ( primo + ultimo ) DIV 2
SE ( v [ centro ] = x ) ALLORA trovato � VERO ALTRIMENTI
SE ( v [ centro ] < x ) ALLORA primo � centro + 1 ALTRIMENTI ultimo � centro – 1 FINE SE
FINE SE
FINE MENTRE RITORNA ( trovato )
Autore : Rio Chierego ( email : riochierego @ libero . it - sito web : www . riochierego . it ) Pag . 7