Esercizio su tempi ordinamento
Ho un esercizio che mi chiede di calcolare e valutare il migliore tra i tempi di ordinamento del mergeSort e radixSort nel caso in cui debba ordinare n interi con massimo valore $k = \Theta ( 2^n )$
Io ho considerato dapprima il mergeSort, esso ordina gli n elementi in tempo $\Theta (nlogn)$ dunque ho considerato il radixSort. Possiamo naturalmente considerare k > n da cui, scelta una base $b = \Theta ( n ) $per la rappresentazione degli interi si ha che il radixSort esegue $log_b k $ chiamate di bucketSort che hanno costo $O(n)$ da cui:
$O( n ) log_b k$ = $ O( n logk / logn ) $ e sfruttando il fatto che $k = \Theta (2^n) $ si ha che il tempo del radixSort è $O( n^2 / logn ) $
Fin qui è giusto?
Poi ho continuato, devo capire quale dei due algoritmi è più efficiente, dunque devo vedere se $\exists \alpha > 0 : \forall n >= n_0$ si ha $n^2 / logn < \alpha n logn$ ovvero se $ n - \alpha log^2 n < 0 \forall n >= n_0 $ Ma si ha che passando al limite il membro sinistro tende a infinito, da cui è impossibile, dunque il mergeSort è più efficiente? E' giusto?
Io ho considerato dapprima il mergeSort, esso ordina gli n elementi in tempo $\Theta (nlogn)$ dunque ho considerato il radixSort. Possiamo naturalmente considerare k > n da cui, scelta una base $b = \Theta ( n ) $per la rappresentazione degli interi si ha che il radixSort esegue $log_b k $ chiamate di bucketSort che hanno costo $O(n)$ da cui:
$O( n ) log_b k$ = $ O( n logk / logn ) $ e sfruttando il fatto che $k = \Theta (2^n) $ si ha che il tempo del radixSort è $O( n^2 / logn ) $
Fin qui è giusto?
Poi ho continuato, devo capire quale dei due algoritmi è più efficiente, dunque devo vedere se $\exists \alpha > 0 : \forall n >= n_0$ si ha $n^2 / logn < \alpha n logn$ ovvero se $ n - \alpha log^2 n < 0 \forall n >= n_0 $ Ma si ha che passando al limite il membro sinistro tende a infinito, da cui è impossibile, dunque il mergeSort è più efficiente? E' giusto?
Risposte
Ciao 
Sì, anche secondo me il tuo procedimento è corretto. Il fatto che ci siano informazioni riguardo al valore massimo che possono assumere gli elementi da ordinare potrebbe inizialmente far pensare che sia preferibile un algoritmo di ordinamento che non utilizzi gli scambi come il radix sort ma queste considerazioni confermano il contrario.
Sì, anche secondo me il tuo procedimento è corretto. Il fatto che ci siano informazioni riguardo al valore massimo che possono assumere gli elementi da ordinare potrebbe inizialmente far pensare che sia preferibile un algoritmo di ordinamento che non utilizzi gli scambi come il radix sort ma queste considerazioni confermano il contrario.
In questo caso il merge sort è chiaramente più efficiente. Ma considera che si tratta di una caso incredibilmente poco realistico. Non riesco infatti a pensare ad alcun caso in cui \(k\) dipenda da \(n\). Normalmente è costante o arbitrario. Inoltre il problema da per scontato che il costo per il confronto e lo scambio non dipendano da \(k\). Ma questo non sembra molto realistico. Lavorando con interi di dimensione arbitraria, il costo per il confronto è verosimilmente lineare in \(k\).. A questo punto anche l'analisi per il merge sort deve probabilmente cambiare..
Si lo so, ma il nostro libro adotta solo ed esclusivamente il criterio di costo uniforme, quindi non credo che in un esercizio ci chieda quello che hai detto
Sì, non credo che si richiedesse di considerare un costo non uniforme sui confronti. Credo volesse solo mostrare che il costo costante del radix sort dipende dal fatto che il massimo è costante.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo