În acest tutorial, veți afla ce sunt notațiile asimptotice. De asemenea, veți afla despre notația Big-O, notația Theta și notația Omega.
Eficiența unui algoritm depinde de cantitatea de timp, stocare și alte resurse necesare pentru executarea algoritmului. Eficiența se măsoară cu ajutorul notațiilor asimptotice.
Este posibil ca un algoritm să nu aibă aceeași performanță pentru diferite tipuri de intrări. Odată cu creșterea dimensiunii intrării, performanța se va schimba.
Studiul modificării performanței algoritmului cu modificarea ordinii dimensiunii intrării este definit ca analiză asimptotică.
Notatii asimptotice
Notările asimptotice sunt notațiile matematice utilizate pentru a descrie timpul de rulare al unui algoritm atunci când intrarea tinde spre o anumită valoare sau o valoare limitativă.
De exemplu: În sortarea cu bule, când matricea de intrare este deja sortată, timpul necesar algoritmului este liniar, adică cel mai bun caz.
Dar, când matricea de intrare este în stare inversă, algoritmul ia timpul maxim (pătratic) pentru a sorta elementele, adică cel mai rău caz.
Când matricea de intrare nu este nici sortată, nici în ordine inversă, atunci este nevoie de timp mediu. Aceste durate sunt notate folosind notații asimptotice.
Există în principal trei notații asimptotice:
- Notare Big-O
- Notare Omega
- Notare Theta
Notare Big-O (notație O)
Notarea Big-O reprezintă limita superioară a timpului de rulare al unui algoritm. Astfel, oferă cel mai rău caz complexitatea unui algoritm.
Big-O dă limita superioară a unei funcții
O (g (n)) = (f (n): există constante pozitive c și n 0 astfel încât 0 ≦ f (n) ≦ cg (n) pentru toate n ≧ n 0 )
Expresia de mai sus poate fi descrisă ca o funcție care f(n)aparține setului O(g(n))dacă există o constantă pozitivă castfel încât să se afle între 0și cg(n), pentru suficient de mare n.
Pentru orice valoare de n, timpul de rulare al unui algoritm nu depășește timpul oferit de O(g(n)).
Deoarece oferă cel mai rău caz de funcționare al unui algoritm, este utilizat pe scară largă pentru a analiza un algoritm, deoarece suntem întotdeauna interesați de scenariul cel mai rău caz.
Notare Omega (notație Ω)
Notarea Omega reprezintă limita inferioară a timpului de rulare al unui algoritm. Astfel, oferă cea mai bună complexitate de caz a unui algoritm.
Omega dă limita inferioară a unei funcții
Ω (g (n)) = (f (n): există constante pozitive c și n 0 astfel încât 0 ≦ cg (n) ≦ f (n) pentru toate n ≧ n 0 )
Expresia de mai sus poate fi descrisă ca o funcție care f(n)aparține setului Ω(g(n))dacă există o constantă pozitivă castfel încât să se afle deasupra cg(n), pentru suficient de mare n.
Pentru orice valoare de n, timpul minim cerut de algoritm este dat de Omega Ω(g(n)).
Notare Theta (notare Θ)
Notarea Theta cuprinde funcția de sus și de jos. Deoarece reprezintă limita superioară și inferioară a timpului de rulare al unui algoritm, este utilizată pentru analiza complexității medii a unui algoritm.
Theta limitează funcția în cadrul factorilor constanți
Pentru o funcție g(n), Θ(g(n))este dată de relația:
Θ (g (n)) = (f (n): există constante pozitive c 1 , c 2 și n 0 astfel încât 0 ≦ c 1 g (n) ≦ f (n) ≦ c 2 g (n) pentru toți n ≧ n 0 )
Expresia de mai sus poate fi descrisă ca o funcție care f(n)aparține setului Θ(g(n))dacă există constante pozitive și astfel încât să poată fi intercalată între și , pentru n suficient de mare.c1c2c1g(n)c2g(n)
Dacă o funcție f(n)se află oriunde între și pentru toate , atunci se spune că este legată asimptotic.c1g(n)c2g(n)n ≧ n0f(n)
