[STRuTTURE DATI] albero decisionale, stranezza?

[thesalien]

Salve a tutti,
ho trovato nel libro una stranezza... c'e scritto che il limite inferiore degli algoritmi di ordinamento e di n log n ma.... l'ordinamento per inserzione nel caso migliore non ordina in un tempo n?????????

[LeleFT]

Immagino che l'autore intenda dire che nel caso peggiore (quello di reale interesse), il limite inferiore è n*log(n), discorso a parte per gli algoritmi non comparativi.


Ciao.

[thesalien]

non c'è scritto nulla a proposito del caso peggiore... cosa intendi per "discorso a parte per gli algoritmi non comparativi."
ps grazie x la risp

[unomichisiada]

Originariamente inviato da thesalien
non c'è scritto nulla a proposito del caso peggiore... cosa intendi per "discorso a parte per gli algoritmi non comparativi."
ps grazie x la risp

Si comunque intende sicuramente nel caso peggiore e lo sottoindente,non ha molto senso considerare il caso migliore ai fini pratici.Ha molto senso considerare quello medio però.

Gli algoritmi non comparativi come dice la parola stessa non ordinano sulla base di confronti tra gli elementi del set da ordinare ma in base ad altri criteri,ne è un esempio il RadixSort (mi pare che si chiami così.. )

[thesalien]

Ho capito... di sicuro verrà sottointeso altrimenti non so che altro pensare... si hai ragione x il Radix sort... CIAO