Salve ragazzi sto preparando l’esame di algoritmi primo anno di informatica mi sono imbattuto in questa osservazione(grazie ai soliti algoritmi come quick sort merge sort heap sort ecc…) che ho notato essere vera ma non riesco a capire e dimostrare in maniera chiara e coincisa il perchè potete aiutarmi ?
Qui la dimostrazione è spiegata bene, ma forse non è quello che cerchi
Puoi considerare l’operazione di sortare un array come trovare una permutazione sortata tra tutte quelle che puo’ assumere
Assumendo che gli elementi siano tutti distinti ci sono n! permutazioni
Naturalmente pero’ non e’ necessario controllare tutte le n! permutazioni ma puoi fare una cosa analoga alla ricerca binaria
Compiendo una comparazione tra 2 elementi in modo ottimale si riesce al massimo a tagliare a meta’ lo spazio di ricerca
La comparazione successiva ottimale puo’ eliminare successivamente meta’ dello spazio di ricerca restante
Questa funzione ha complessita’ O(log2(n!)) = O(log2(n) + log2(n-1) + … log2(1)) = O(n*log2(n))