Algoritmica

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)