Record imbattibile e lower bound
Ciao a tutti 
avrei una dubbio su record imbattibile e lower bound...
a quanto ho capito, il record imbattibile ci dice che l'altezza di un albero binario sarà al minimo $log n$ ed al massimo $n$.
Questo significa che algoritmi che dividono in due il problema andranno a formare un albero binario di altezza h saturo fino al lv h-1, mentre, algoritmi che non dividono in due il problema potrebbero andare a formare un albero degenere.
Da qui deriva il lower bound che ci dice che un algoritmo di ordinamento non potrà mai richiedere costo mino
re di $nlogn + o(n logn)$.
ecco...io vorrei sapere se quello che ho detto è giusto o se non ho capito niente XD.
Grazie mille in anticipo!!!
Ciao
avrei una dubbio su record imbattibile e lower bound...
a quanto ho capito, il record imbattibile ci dice che l'altezza di un albero binario sarà al minimo $log n$ ed al massimo $n$.
Questo significa che algoritmi che dividono in due il problema andranno a formare un albero binario di altezza h saturo fino al lv h-1, mentre, algoritmi che non dividono in due il problema potrebbero andare a formare un albero degenere.
Da qui deriva il lower bound che ci dice che un algoritmo di ordinamento non potrà mai richiedere costo mino
re di $nlogn + o(n logn)$.
ecco...io vorrei sapere se quello che ho detto è giusto o se non ho capito niente XD.
Grazie mille in anticipo!!!
Ciao
Risposte
La limitazione inferiore $\Omega(nlogn)$ non è derivato direttamente da un albero qualunque. Deriva dalla limitazione di $n!$. Prova a cercare "albero decisionale".
ah ok...grazie mille!!!
comunque per il resto è giusto???
comunque per il resto è giusto???
cosa intendi con questo:
puoi crearti un algoritmo che dividi in tre un vettori e vai in ricorsione, non vedo problemi.
Forse hai confusione tra l'algoritmo merge-sort (es. di suddivisione in due parti) che ha come complessità ottima $O(nlog_2(n))$ e la limitazione del problema dell'ordinamento basato su confronti $Omega(nlog_2(n))$:
Il primo deriva dalla ricorrenza di merg-sort: $2T(n/2) + \Theta(n)$
il secondo dalla limitazione inferiore $n!$ che sarebbero le permutazioni possibili di un confronto, derivato ancora dall'albero delle scelte dove ha altezza minima $log_2(n!)$ che ha limitazione inferiore $Omega(nlog_2n)$ (vedi qui per una dimostrazione).
Se spieghi meglio cosa ti confonde vediamo di sistemare i tuoi dubbi
algoritmi che non dividono in due il problema potrebbero andare a formare un albero degenere.
puoi crearti un algoritmo che dividi in tre un vettori e vai in ricorsione, non vedo problemi.
Forse hai confusione tra l'algoritmo merge-sort (es. di suddivisione in due parti) che ha come complessità ottima $O(nlog_2(n))$ e la limitazione del problema dell'ordinamento basato su confronti $Omega(nlog_2(n))$:
Il primo deriva dalla ricorrenza di merg-sort: $2T(n/2) + \Theta(n)$
il secondo dalla limitazione inferiore $n!$ che sarebbero le permutazioni possibili di un confronto, derivato ancora dall'albero delle scelte dove ha altezza minima $log_2(n!)$ che ha limitazione inferiore $Omega(nlog_2n)$ (vedi qui per una dimostrazione).
Se spieghi meglio cosa ti confonde vediamo di sistemare i tuoi dubbi
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo