|
Poiché questo tipo di misurazione è molto dettagliata, quindi di solito difficilmente applicabile alla realtà, si introducono delle approssimazioni che permettono di operare su [[algoritmo|algoritmi]] più astratti. In particolare si ricorre alla notazione <math>O(\cdot)</math> ([[O-grande|'''O grande''']]). Formalmente:
:<math>gf(n)\in = O(fg(n))</math> se <math>\exists (n_{0}, c)</math> tali che <math>c\ge 0</math>, <math>n_0\ge 0</math>, <math>\forall n>n_0</math> <math>gf(n) \le cfc g(n)</math>
In parole povere, laLa funzione <math>gf(n)</math> da un certo <math>n</math> in poi cresce al più come la funzione <math>fg(n)</math>. Per fare un esempio, <math>n^2+2n+4 \in O(n^2)</math> perché possiamo trovare una coppia di costanti <math>(n_0, c)</math> che soddisfano la condizione sopra. Si dice quindi che un algoritmo opera in tempo <math>O(f(n))</math> se termina in un tempo proporzionale a <math>f(n)</math> dato un input di dimensione <math>n</math>.
Per valutare le prestazioni di un algoritmo, solo in parte legate alla classificazione di un problema, è utile distinguere alcuni casi: si considerano il ''caso ottimo'', il ''caso peggiore'' e il ''caso medio''.
In questo ambito tornano dunque utili altre due misure, complementari della notazione ''O grande'':
* <math>g(n)\in = \Omega(f(n))</math> se <math>\exists (n_{0}, c)</math> tali che <math>c\ge 0</math>, <math>n_0\ge 0</math>, <math>\forall n>n_0</math> <math>g(n) \ge cf(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)\in = \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.
==Classi di complessità==
| 