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 nVediamo 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<AChiatamente 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<CCon 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<CIn 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 2h dove h è l'altezza dell'albero stesso, sia ha che per coprire tutte le possibili permutazioni deve essere valida la seguente formula2h > n!Quindi sapendo chen! > n/2n/2ed applicando il logaritmoh > (n/2) log (n/2)da cui è facile dedurre cheh = omega(n log n)
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 nVediamo 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<AChiatamente 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<CCon 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<CIn 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 2h dove h è l'altezza dell'albero stesso, sia ha che per coprire tutte le possibili permutazioni deve essere valida la seguente formula2h > n!Quindi sapendo chen! > n/2n/2ed applicando il logaritmoh > (n/2) log (n/2)da cui è facile dedurre cheh = omega(n log n)