9 : Analisi degli Algoritmi Vers . 2.0 – Aprile 2022
- Caso pessimo : il numero di passi ( confronti ) da effettuare è il numero K equivalente al numero di divisioni che consente di arrivare all ’ ultimo elemento dell ’ insieme ossia continuo a dividere N finché quello che rimane è un solo elemento ossia N / 2 / 2 / 2 /…/ 2 = 1 allora ho N / 2 k = 1 ossia N = 2 k ossia K = log2N quindi
Tpessimo ( N ) = log2N
- Caso ottimo ossia Tottimo ( N ) = 1 quando l ’ elemento da ricercare si trova esattamente nella posizione N / 2
- Caso medio ossia Tmedio ( N ) = ( 1 + log2N )/ 2 che appartiene comunque alla famiglia computazionale log2 N
|
Ricerca sequenziale |
Ricerca binaria |
|
1 |
1 |
Caso pessimo |
N |
log2 N |
Caso medio |
N / 2 |
1 + log2 N |
N . B . Come è possibile osservare gli algoritmi hanno la stessa complessità nel caso ottimo , ma complessità diverse nel caso medio e nel caso pessimo .
In caso di ricerca di un elemento in un insieme ordinato , la maggiore efficienza dell ’ algoritmo di ricerca binaria o dicotomica rispetto a quello di ricerca sequenziale è plasticamente rappresentato dai dati presenti in questa tabella che specificano i numeri di confronti effettuati dai due algoritmi NEL CASO MEDIO al crescere della dimensione N dei dati del problema
L ’ obiettivo di un buon programmatore sarà quello di risolvere un problema scrivendo un algoritmo con la minima complessità possibile sia al caso medio sia a quello pessimo : definiremo tale algoritmo un algoritmo ottimo .
Pertanto per complessità di un problema intenderemo la complessità degli algoritmi ottimi che risolvono quel problema ( e spesso tale complessità è già nota a priori ).
Autore : Rio Chierego ( email : riochierego @ libero . it - sito web : www . riochierego . it ) Pag . 9