Calcolo della complessità: caso migliore e caso peggiore

[dungedra]

mi potreste dire cosa si fa quando si ricercano le complessità nel caso migliore e nel caso peggiore

E' nel caso peggiore che che devo ricercare l'upper bound??

Per favore fatemi un po di chiarezza

[Kaamos]

Originariamente inviato da dungedra
mi potreste dire cosa si fa quando si ricercano le complessità nel caso migliore e nel caso peggiore

E' nel caso peggiore che che devo ricercare l'upper bound??

Per favore fatemi un po di chiarezza

Perché hai postato nella sezione Java? E' una cosa indipendente dal linguaggio.

Online ci sono tonnellate di appunti, dispense e quant'altro sull'argomento, dacci un'occhiata e poi cerca di fare una domanda più specifica.

L'analisi si può fare partendo da diverse supposizioni: se devo inserire in una lista concatenata semplice, il caso migliore sarà l'ipotesi in cui debba inserire in testa (Θ(1)), mentre il caso peggiore (supponendo di non avere puntatori all'ultimo elemento) sarà quello in cui debba inserire in fondo, dovendo quindi visitare tutta la lista (Θ(n) con n dimensione della lista).

"upper bound" e "lower bound" non c'entrano col caso peggiore/migliore/medio. Una volta scelto quale di questi casi analizzare, la complessità avrà un limite superiore (notazione O grande) e un limite inferiore (notazione Ω). Per esempio, il suddetto inserimento (considerando sia caso peggiore che migliore) è in O(n) perché non si fanno mai più di O(n) operazioni. Oppure, è provato che un algoritmo di ordinamento per comparazione (insertion sort, bubble sort, ...) nel caso peggiore è in Ω(n·log(n)), quindi se devi analizzarne la complessità sai già che non sarà inferiore a quella. Queste due notazioni sono limiti "inclusivi", O(n) significa che l'algoritmo potrebbe fare n operazioni

[LeleFT]

Ho spostato la discussione nel forum "Programmazione", essendo un argomento slegato dal singolo linguaggio.


Ciao.