9 : Analisi degli Algoritmi Vers . 2.0 – Aprile 2022
Ricerca di un elemento x : Algoritmo RICERCA SEQUENZIALE x = 2
x = 12
Ipotizziamo ora che gli elementi dell ’ insieme siano 100 - Caso ottimo ossia Tottimo ( N ) = 1 - Caso pessimo ossia Tpessimo ( N ) = 100 - Caso medio ossia Tmedio ( N ) = ( se l ’ elemento è nella prima posizione il numero dei tentativi è 1 ) + ( se l ’ elemento è nella seconda posizione il numero dei tentativi è 2 ) + ecc .. = ( 1 + 2 + 3 + …+ 100 ) / 100
Più in generale , se ipotizziamo che gli elementi dell ’ insieme siano N , allora il caso medio ( pari al numero di confronti medio da effettuare per trovare l ’ elemento ) sarà espresso dalla relazione :
Tmedio ( N ) = ( 1 + 2 + 3 + …+ N ) / N Poiché ( 1 + 2 + 3 + …+ N ) = N * ( N + 1 )/ 2 sostituendo avremo
Tmedio ( N ) = ( N + 1 )/ 2 che se N è 100 vale 50 poiché ( 100 + 1 )/ 2 = 50.5 ed arrotondiamo per difetto
Ricerca di un elemento x in un insieme ORDINATO : Algoritmo RICERCA BINARIO
Si suppone di avere un insieme ordinato di valori ( esempio elenco telefonico ) e di volerne cercare uno al suo interno ( esempio " Mario Rossi ").
Si suppone di dividere l ’ insieme ordinato in due parti e vedere se il valore cercato cade nella prima parte dell ’ insieme o nella seconda . Si identifica così la parte dell ’ insieme ordinato su cui lavorare e si procede ricorsivamente ossia applicando lo stesso procedimento al risultato del passo precedente .
In questo modo si scarta tutta la parte di elementi che sicuramente sono inutili ai nostri fini e ci si concentra sulla parte utile
Si riduce il problema della metà ( circa ) a ogni interazione limitando la ricerca alla parte precedente o alla parte successiva del valore che si trova a metà dell ’ insieme ( nel suo centro ).
Ogni tentativo permette di ridurre l ’ ampiezza del problema di un fattore 2 ( percio detto " binario "). Il primo tentativo riduce il numero degli elementi da confrontare a N / 2 ; il secondo a N / 4 , il terzo a N / 8 , e così via . Quindi :
Autore : Rio Chierego ( email : riochierego @ libero . it - sito web : www . riochierego . it ) Pag . 8