8 : I dati e la loro struttura nella programmazione ( ARRAY , MATRICI , RECORD ) Vers . 8.2 – Settembre 2022
LE DUE STRATEGIE DI RICERCA A CONFRONTO
Ipotizziamo di avere assegnato il seguente vettore o array monodimensionale v ordinato in senso crescente e con dimensione n = 8
Si può ossevare che :
-9 -3 1 7 11 14 19 22
1 2 3 4 5 6 7 8
- applicando il processo risolutivo dettagliato nell ’ algoritmo di ricerca sequenziale , per poter trovare l ’ elemento assegnato : � nel CASO FAVOREVOLE ( ossia elemento al primo posto , es -9) si effettuerà esattamente 1 confronto ; � nel CASO PESSIMO ( ossia elemento all ’ ultimo posto , es . 22 ) si effettueranno esattamente 8 ( ossia n ) confronti ; � nel CASO MEDIO si effettueranno un numero di confronti pari a ( CASO FAVOREVOLE + CASO PESSIMO ) / 2 ( ossia pari ad ( 1 + n ) / 2 ossia 5 che può approssimarsi a 4 ossia a n / 2 );
- applicando il processo risolutivo dettagliato nell ’ algoritmo di ricerca binaria o dicotomica , per poter trovare l ’ elemento assegnato : � nel CASO FAVOREVOLE ( ossia elemento nel posto centrale , es 7 ) si effettuerà esattamente 1 confronto ; � nel CASO PESSIMO ( ossia elemento all ’ ultimo posto , es 22 ) si effettueranno esattamente 3 ( ossia log 2 ( n )) confronti ; � nel CASO MEDIO si effettueranno un numero di confronti pari a ( CASO FAVOREVOLE + CASO PESSIMO ) / 2 ( ossia pari ad ( 1 + log 2 ( n )) / 2 ossia 4 che può approssimarsi a 3 ossia a log 2 ( n ));
Si deduce che l ’ algoritmo di ricerca binaria o dicotomica , quando il numero di elementi n è pari a 8 , sia più efficiente rispetto all ’ algoritmo ( equivalente ) di ricerca sequenziale .
In realtà quando studieremo più avanti l ’ analisi computazionale degli algoritmi , dimostreremo che , qualunque sia il valore assunto da n , l ’ algoritmo di ricerca binaria o dicotomica risulterà essere sempre più efficiente rispetto a quello di ricerca sequenziale .
Diamo un ’ occhiata al seguente grafico :
3 4 v
T ( n ) indica la complessità computazionale di un algoritmo ( o complessità ) ossia la funzione matematica che indica la relazione esistente tra il numero di operazioni effettuate da un algoritmo ( programma ) e la dimensione n dei dati ricevuti in input .
T Ricerca Sequenziale ( n ) = n / 2 T Ricerca Binaria ( n ) = log 2 ( n )
Confrontanto " empiricamente " i due grafici si nota come qualunque sia il valore della dimensione n del problema ( ossia il numero di elementi del vettore ), i valori di complessità calcolati con le rispettive funzioni matematiche , differiscano sempre .
Ciò che emerge è che , a parità di dimensione del problema ( ossia a parità del numero n di elementi contenuti nel vettore ) ed al crescere dello stesso , risulterà sempre verificata la seguente disequazione :
TRicerca Binaria ( n ) < TRicerca Sequenziale ( n )
Da tutto quanto illustrato consegue che , in caso di vettori già ordinati , l ’ algoritmo di ricerca binaria o dicotomica risulta essere , al crescere della dimensione del problema , più efficiente rispetto all ’ algoritmo ( equivalente ) di ricerca sequenziale .
Autore : Rio Chierego ( email : riochierego @ libero . it - sito web : www . riochierego . it ) Pag . 33