Esercizi sulla notazione asintotica
-
Eʼ possibile che un algoritmo abbia tempo di esecuzione O(n2) nel caso peggiore e Ω(n)
nel caso migliore?
Se un algoritmo ha tempo di esecuzione Ω(n2) nel caso peggiore, è possibile che nel caso
migliore lʼalgoritmo abbia complessità O(n log n)?
Se un algoritmo ha tempo di esecuzione Ω(n) e O(n) nel caso peggiore, possiamo
concludere che nel caso peggiore è Θ(n)?
Se la complessità di un problema è Ω(n2) nel caso peggiore, e si dispone di un algoritmo
che risolve il problema in tempo O(n2) nel caso peggiore, si può affermare che lʼalgoritmo
ha tempo di esecuzione Θ(n2) nel caso peggiore?
Potrebbero interessarti anche ...
-
Risposte: 1
Ultimo Post: 31-05-2012, 21:53
-
Risposte: 14
Ultimo Post: 20-07-2011, 14:25
-
Risposte: 0
Ultimo Post: 16-04-2011, 02:34
-
Risposte: 1
Ultimo Post: 21-03-2010, 11:37
-
Risposte: 0
Ultimo Post: 01-07-2009, 12:09