Domanda veloce su algoritmi di ordinamento
Un esercizio mi chiede:
Dimostrare che ogni algoritmo di ordinamento basato su confronti esegue nel caso peggiore $ \Omega(n log_2(n)) $ confronti.
Ora,partendo dal fatto che di algoritmi di ordinamento con complessità $ \Theta(n log_2(n)) $ tra quelli più comuni abbiamo l'Heap Sort,il Merge Sort e il Quicksort (anche se quest'ultimo nel caso peggiore ha $ \Theta(n^2) $,senza avere davanti lo pseudocodice e conoscendo soltanto il comportamento dall'algoritmo,in che modo lo dimostro?
posso dire che dato che questi 3 algoritmi operano in maniera ricorsiva suddividendo il problema in sottoproblemi (divide et impera) la complessità è dunque $ \Theta(n log_2(n)) $ ? altrimenti come dovrei rispondere?
P.S: perchè nella richiesta il caso peggiore viene indicato con Omega?
P.S 2: domani ho l'esame
Dimostrare che ogni algoritmo di ordinamento basato su confronti esegue nel caso peggiore $ \Omega(n log_2(n)) $ confronti.
Ora,partendo dal fatto che di algoritmi di ordinamento con complessità $ \Theta(n log_2(n)) $ tra quelli più comuni abbiamo l'Heap Sort,il Merge Sort e il Quicksort (anche se quest'ultimo nel caso peggiore ha $ \Theta(n^2) $,senza avere davanti lo pseudocodice e conoscendo soltanto il comportamento dall'algoritmo,in che modo lo dimostro?
posso dire che dato che questi 3 algoritmi operano in maniera ricorsiva suddividendo il problema in sottoproblemi (divide et impera) la complessità è dunque $ \Theta(n log_2(n)) $ ? altrimenti come dovrei rispondere?
P.S: perchè nella richiesta il caso peggiore viene indicato con Omega?
P.S 2: domani ho l'esame
Risposte
L'idea è che la complessità nel caso peggiore di un algoritmo di ordinamento basato sui confronti non possa mai scendere sotto \(n\,\log\,n\). Quella nel caso migliore può ovviamente essere più bassa (anche se non è il caso degli algoritmi da te elencati). Ma ti hanno chiesto di dimostrarlo per esercizio?
"apatriarca":l'esercizio consiste in quella riga in grassetto che vedi nel primo post di questa discussione,presumo che basti una risposta di tipo teorico non troppo nel dettaglio,anche perchè non è possibile consultare lo pseudocodice (tantomeno è impossibile ricordare lo pseudocodice di 6 algoritmi a memoria).Comunque non ho capito perchè l'idea è che la complessità nel caso peggiore di un algoritmo di ordinamento basato sui confronti non possa mai scendere sotto \(n\,\log\,n\) ,in base a cosa si può dirlo?
L'idea è che la complessità nel caso peggiore di un algoritmo di ordinamento basato sui confronti non possa mai scendere sotto \(n\,\log\,n\). Quella nel caso migliore può ovviamente essere più bassa (anche se non è il caso degli algoritmi da te elencati). Ma ti hanno chiesto di dimostrarlo per esercizio?
E' un risultato teorico abbastanza importante. La dimostrazione consiste nell'osservare che ad ogni algoritmo di ordinamento basato sul confronto corrisponde un albero in cui ad ogni nodo interno si esegue un confronto e ad ogni foglia corrisponde una partizione diversa della successione in input. Siccome il numero di foglie deve essere almeno \(n!\), si arriva alla conclusione che l'altezza di tale albero è almeno \(n\,log\,n\). Si trova sicuramente nel tuo libro di algoritmi.
mini aggiunta:
che è derivato che l'altezza minima dell'albero delle scelte è $log(n!)$
una dimostrazione è anche qui.
"apatriarca":
si arriva alla conclusione che l'altezza di tale albero è almeno \(n\,log\,n\).
che è derivato che l'altezza minima dell'albero delle scelte è $log(n!)$
una dimostrazione è anche qui.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo