Notatia O (O mare)

Notatia O (O mare)

Notatia O desemneaza marginea asimptotica superioara a unei functii. Pentru o functie data g(n), se defineste O(g(n)) ca si multimea de functii:

O(g(n)) = [2.3.2.a]

Notatia O se utilizeaza pentru a desemna o margine superioara a unei functii in interiorul unui factor constant.

Pentru toate valorile n superioare lui n₀ , valoarea functiei f(n) este pe sau dedesubtul lui g(n) (fig.2.3.b ).

Pentru a preciza ca o functie f(n) este membra a lui O(g(n)) se utilizeaza notatia f(n) = O(g(n)).

Faptul ca f(n) este Q(g(n)) implica ca  f(n) = O(g(n)) deoarece notatia Q este mai puternica decat notatia O. Formal acest lucru se precizeaza prin relatia [2.3.2.b].

Q(g(n)) O(g(n))  

In consecinta, deoarece s-a demonstrat faptul ca orice functie patratica  a n ² + b n + c , a > 0 este Q(n ² , in baza relatiei [2.3.2.b] rezulta ca aceasta functie este implicit si O(n ²).

Este surprinzator faptul ca din aceleasi considerente, functia liniara a n  + b este de asemenea O(n ²), lucru usor de verificat daca se alege  c = a + | b | si n₀ = 1.

Notatia O este de obicei cea mai utilizata in aprecierea timpului de executie al algoritmilor respectiv a performantei acestora.

Ea poate fi uneori apreciata direct din inspectarea structurii algoritmului, spre exemplu existenta unei bucle duble conduce imediat la o margine de ordinul O(n ²)

Deoarece notatia O descrie o margine superioara, cand este utilizata pentru a margini cazul cel mai defavorabil de executie al unui algoritm, prin implicatie ea margineste superior comportamentul algoritmului in aceeasi masura pentru orice intrare.

In cazul notatiei Q lucrurile difera.

o      Spre exemplu, daca Q(n² margineste superior cel mai defavorabil timp de executie al unui algoritm de sortare prin insertie, aceasta nu inseamna ca Q(n² margineste orice intrare.

o      Astfel, daca intrarea este gata sortata, algoritmul dureaza un timp proportional cu Q(n)

Tehnic vorbind, afirmatia ca timpul de executie al unui algoritm de sortare este O(n²) constituie un abuz de limbaj.

Corect: indiferent de configuratia intrarii de dimensiune n, pentru orice valoare a lui n timpul de executie al algoritmului pentru setul corespunzator de intrari este O(n²).

Cele mai obisnuite ordine de marime ale notatiei O se afla in relatiile de ordine prezentate in [2.3.2.c], iar reprezentarea lor grafica la scara logaritmica apare in fig.2.3.c.

O(1) < O(log  n) < O(n) < O(n log n) < O(n²) < O(n³) <
 < O(2ⁿ) < O(10 ⁿ) < O( n ! ) < O(n ⁿ)                       [2.3.2.c]

Fig. 2.3.c. Ordine de marime ale notatiei O

In acelasi context in [2.3.2.d] se prezinta cateva sume intregi utile care sunt frecvent utilizate in calculul complexitatii algoritmilor.

[2.3.2.d]