If you're seeing this message, it means we're having trouble loading external resources on our website.

Dacă sunteţi în spatele unui filtru de web, vă rugăm să vă asiguraţi că domeniile *. kastatic.org şi *. kasandbox.org sunt deblocate.

Conţinutul principal

Funcțiile în notația asimptotică

Atunci când folosim notația asimptotică pentru a exprima ordinul de creștere al timpului de execuție al unui algoritm în funcție de n, dimensiunea datelor de intrare, este bine să avem în vedere câteva lucruri.
Să începem cu ceva ușor. Să presupunem că un algoritm se execută în timp constant, indiferent de dimensiunea datelor de intrare. De exemplu, dacă primești un vector care este deja sortat crescător și trebuie să găsești cel mai mic element, operațiile pe care le faci necesită timp constant, pentru că minimul se află pe pozița 0. Din moment ce preferăm să folosim o funcție cu n pentru notația asimptotică, am putea spune că acest algoritm se execută în Θ(n0) timp. De ce? Pentru că n0=1, iar timpul de execuție al algoritmului aparține termenului constant 1. În practică, nu scriem Θ(n0), ci Θ(1).
Acum să presupunem că un algoritm se execută în Θ(log10n) timp. Ai putea spune și că se execută în Θ(log2n) timp. De fiecare dată când baza logaritmului este o constantă, nu contează în ce bază folosim notația asimptotică. De ce nu? Pentru că există o formulă matematică ce spune că
logan=logbnlogba
pentru toate numerele pozitive a, b și n. Așadar, dacă a și b sunt constante, atunci logan și logbn diferă doar prin termenul logba, iar acesta este o constantă pe care o putem ignora la notația asimptotică.
Așadar, putem spune că timpul de execuție al căutării binare în cazul cel mai nefavorabil este Θ(logan) pentru orice constantă pozitivă a. De ce? Numărul de încercări este cel mult log2n+1, generarea și testarea fiecărei încercări are timp constant, iar actualizarea și returnarea au și ele timp constant. Cu toate acestea, în practică, deseori scriem că Θ(log2n) este timpul de execuție al căutării binare, deoarece informaticienii preferă să exprime valorile în funcție de puterile lui 2.
Există o ordine a funcțiilor pe care o întâlnim adesea atunci când analizăm algoritmii folosind notația asimptotică. Dacă a și b sunt constante și a<b, atunci timpul de execuție Θ(na) crește mai lent decât timpul Θ(nb). De exemplu, un timp de execuție Θ(n), egal cu Θ(n1), crește mai lent decât un timp de execuție Θ(n2). Exponenții nu trebuie să fie în mod obligatoriu întregi. De exemplu, un timp de execuție Θ(n2) crește mai lent decât Θ(n2n), care este egal cu Θ(n2.5).
Următorul grafic compară creșterile pentru n,n2, și n2.5:
Grafic ce compară n, radical din n și n la puterea 2.5
Logaritmii cresc mai lent decât polinomialele. Adică Θ(log2n) crește mai lent decât Θ(na) pentru orice constantă pozitivă a. Însă, din moment ce valoarea lui log2n se mărește pe măsură ce n se mărește, Θ(log2n) crește mai repede decât Θ(1).
Următorul grafic compară creșterile pentru 1, n și log2n:
Grafic ce compară 1, logaritm în baza 2 de n și n
Iată o listă cu funcțiile pe care le întâlnim cel mai des atunci când folosim notația asimptotică pentru analiza algoritmilor, ordonate de la cea mai lentă până la cea mai rapidă din punct de vedere al creșterii:
  1. Θ(1)
  2. Θ(log2n)
  3. Θ(n)
  4. Θ(nlog2n)
  5. Θ(n2)
  6. Θ(n2log2n)
  7. Θ(n3)
  8. Θ(2n)
  9. Θ(n!)
Ține minte că funcția exponențială an, unde a>1, crește mai repede decât orice funcție polinomială nb, unde b este o constantă oarecare.
Lista de mai sus nu este completă, deoarece există multe funcții ale căror timpi de execuție nu sunt trecuți aici. Sperăm că vei întâlni și tu câteva în cariera ta de programator.

Acest conținut este o colaborare a profesorilor Thomas Cormen și Devin Balkcom, de la Dartmouth Computer Science, cu echipa de elaborare a curriculumului de informatică de la Khan Academy. Conținutul este licențiat CC-BY-NC-SA.