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.

Elementi ripetuti in un vettore

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 + ..... 2+1 operazioni.
Ricordando che 1+2+...+n è uguale a n*(n+1)/2 l'algoritmo ha complessità O(n²)

Seconda soluzione
Si ordina preventivamente il vettore e poi si verifica se due elementi consecutivi sono uguali.
Quindi, sapendo che  il costo dell'ordinamento è O(n*log n) e lo scorrimento è O(n), otteniamo un costo totale di O(n*log n).

Terza soluzione
Questa soluzione è applicabile nel caso in cui i valori del vettore siano numeri interi.
Si crea un vettore di appoggio W lungo quanto il massimo elemento presente nel vettore V da controllare. Si scorre V e per ogni elemento si va ad incrementare il valore contenuto nella cella di W indicizzata dall'elemento V[i].
Se in qualsiasi momento si ha che il contenuto di una cella di W diventa 2 allora questo indica che l'elemento corrispondete all'indice è presente due volte in V.
Complessità O(n).

Stabilire se due parole sono anagrammi una dell'altra

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 e per ogni lettere si incrementa il contatore nella cella corrispondente alla lettera.
Successivamente si scorre la seconda parola ed in questo caso si decrementa il contatore corrispondente.

Alla fine dei due cicli la struttura di appoggio deve contenere tutti contatori a zero.

Complessità O(n) ottimo.

Ordinamento di un vettore tramite confronti

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à è Omega(n log n). Visto che abbiamo l'algoritmo MergeSort che ha complessità O(n log n) sappiamo che il problema ha complessità

n log n

Vediamo come ottenere questo risultato.

Supponiamo di avere tre elementi A,B,C e suppuniamo per semplicità che siano tutti distinti. Effettuano il primo confronto possiamo ottenere i seguenti casi.

                                  A<B                 B<A

Chiatamente questo non ci basta per avere l'ordinamento, quindi effettuiamo un secondo confronto tra A e C che ci porta ad ottenere.

                                 A<B                  B<A

                      C<A           A<C       C<A         A<C

Con un terzo confronto

                                 A<B                                       B<A

                      C<A           A<C                       C<A         A<C

             B<C        C<B    B<C  C<B          C<B    B<C    C<B     B<C

In questa maniera abbiamo trovato tutti i possibili ordinamenti dei tre elementi.

Analizzando questo esempio ci rendiamo conto che ogni foglia del nostro albero corrisponde ad una particolare permutazione dei tre elementi. Quindi, tenendo conto che il numero delle foglie in un albero binario cresce come 2^h dove h è l'altezza dell'albero stesso, sia ha che per coprire tutte le possibili permutazioni deve essere valida la seguente formula

2^h > n!

Quindi sapendo che

n! > n/2^n/2

ed applicando il logaritmo

h > (n/2) log (n/2)

da cui è facile dedurre che

h = omega(n log n)

Salve

Salve a tutti,

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