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…

Altro problema tipico. Verificare se in un vettore sono presenti due elementi uguali.Prima soluzione.Prendo il primo elemento e scorro il resto del vettore per vedere se questo è presente, poi prendo il secondo elemento e verifico se è presente nei restanti n-2 elementi e così di seguito.Nel caso pessimo abbiamo n-1 + n-2 + .....…

Supponiamo di avere due parole e di dover verificare se una è anagramma dell'altra.Ovviamente le parole devono avere la stessa lunghezza, altrimenti la verifica è banale.La soluzione più performante è quella di creare una struttura di appoggio, tipicamente un vettore, indicizzato con le lettere dell'alfabeto o con la loro trasposizione numerica.Si scorre la prima parola…

La prima cosa da analizzare quando si affronta un problema è la complessità del problema stesso, in particolare è necessario stabilire un limite inferiore alla complessità in modo da riuscire a stabilire quando una soluzione algoritmica non è ulteriormente migliorabile.Ad esempio nel caso dell'ordinamento di un vettore tramite confronti è possibile dimostrare che la complessità…

Salve a tutti,da oggi inizio a gestire questo blog dedicato all'Algoritmica ed alle Strutture Dati.