Algoritmica

Ricerca lineare e ammortizzamento dei costi

Analiziamo adesso un semplice esempio che ci può far capire come una corretta analisi del problema può far migliorare sensibilmente le performance.

Supponiamo di dover effettuare una ricerca su di una struttura lineare senza alcun ordinamento.
Non avendo la struttura nessuna particolarità e necessario scorrere gli elementi sequenzialmente con un costo proporzionale a N.
Supponiamo che si debba effettuare una seconda ricerca, il costo è sempre proporzionale a N.

Se viene effettuata l'ordinamento del vettore prima di effettuare la ricerca a quel punto ogni successiva ricerca ha costo log N.

Facciamo qualche esempio numerico.

Supponiamo che gli elementi siano 1000, una ricerca lineare in media costerebbe 500 accessi, ordinare il vettore costerebbe 1000 * log 1000 quindi circa 10.000 e le successive ricerche costerebbero 10 accessi.
Facendo un rapido calcolo con venti accessi avremmo ammortizzato il costo dell'ordinamento e da quel momento in poi avremmo un costo di 50 volte inferiore.

Questo fa chiaramente capire è sempre bene cercare di organizzare i dati in base al numero di operazioni da effettuare ed è sempre bene tenere conto dell'ammortamento del costo delle operazioni.