Teoria della complessità computazionale: differenze tra le versioni

Contenuto cancellato Contenuto aggiunto
Botcrux (discussione | contributi)
m Bot: fix template {{sezione vuota}}
Riga 31:
In questo ambito tornano dunque utili altre due misure, complementari della notazione ''O grande'':
 
* <math>g(n) = \Omega(f(n))</math> se <math>\exists (n_{0}, c)</math> tali che <math>c > 0</math>, <math>n_0\ge 0</math>, <math>\forall n>n_0</math> <math>fg(n) \ge cgcf(n)</math>, cioè <math>g(n)</math> cresce non più lentamente di <math>f(n)</math>; questa notazione è utile per valutare il caso ottimo di un algoritmo: se un algoritmo è <math>\Omega(f(n))</math> ("Omega di <math>f(n)</math>") significa che nel caso migliore richiede <math>f(n)</math> passi per essere risolto.
* <math>g(n) = \Theta(f(n))</math> se <math>g(n)\in O(f(n))</math> e <math>g(n)\in \Omega(f(n))</math>, cioè <math>g(n)</math> cresce altrettanto rapidamente di <math>f(n)</math>. Se un algoritmo è <math>\Theta(f(n))</math> ("Theta di <math>f(n)</math>"), non ci sono variazioni significative di prestazioni tra il caso migliore e il caso peggiore.