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$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$n pentru notația asimptotică, am putea spune că acest algoritm se execută în $\Theta(n^0)$\Theta, left parenthesis, n, start superscript, 0, end superscript, right parenthesis timp. De ce? Pentru că $n^0 = 1$n, start superscript, 0, end superscript, equals, 1, iar timpul de execuție al algoritmului aparține termenului constant 1. În practică, nu scriem $\Theta(n^0)$\Theta, left parenthesis, n, start superscript, 0, end superscript, right parenthesis, ci $\Theta(1)$\Theta, left parenthesis, 1, right parenthesis.

Acum să presupunem că un algoritm se execută în $\Theta(\log_{10} n)$\Theta, left parenthesis, log, start base, 10, end base, n, right parenthesis timp. Ai putea spune și că se execută în $\Theta(\log_2 n)$\Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis 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ă

pentru toate numerele pozitive $a$a, $b$b și $n$n. Așadar, dacă $a$a și $b$b sunt constante, atunci $\log_a n$log, start base, a, end base, n și $\log_b n$log, start base, b, end base, n diferă doar prin termenul $\log_b a$log, start base, b, end base, a, 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 $\Theta(\log_a n)$\Theta, left parenthesis, log, start base, a, end base, n, right parenthesis pentru orice constantă pozitivă $a$a. De ce? Numărul de încercări este cel mult $\log_2 n + 1$log, start base, 2, end base, n, plus, 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ă $\Theta(\log_2 n)$\Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis 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$a și $b$b sunt constante și $a < b$a, is less than, b, atunci timpul de execuție $\Theta(n^a)$\Theta, left parenthesis, n, start superscript, a, end superscript, right parenthesis crește mai lent decât timpul $\Theta(n^b)$\Theta, left parenthesis, n, start superscript, b, end superscript, right parenthesis. De exemplu, un timp de execuție $\Theta(n)$\Theta, left parenthesis, n, right parenthesis, egal cu $\Theta(n^1)$\Theta, left parenthesis, n, start superscript, 1, end superscript, right parenthesis, crește mai lent decât un timp de execuție $\Theta(n^2)$\Theta, left parenthesis, n, squared, right parenthesis. Exponenții nu trebuie să fie în mod obligatoriu întregi. De exemplu, un timp de execuție $\Theta(n^2)$\Theta, left parenthesis, n, squared, right parenthesis crește mai lent decât $\Theta(n^2 \sqrt{n})$\Theta, left parenthesis, n, squared, square root of, n, end square root, right parenthesis, care este egal cu $\Theta(n^{2.5})$\Theta, left parenthesis, n, start superscript, 2, point, 5, end superscript, right parenthesis.

Următorul grafic compară creșterile pentru $n$n,$n^2$n, squared, și $n^{2.5}$n, start superscript, 2, point, 5, end superscript:

Logaritmii cresc mai lent decât polinomialele. Adică $\Theta(\log_2 n)$\Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis crește mai lent decât $\Theta(n^a)$\Theta, left parenthesis, n, start superscript, a, end superscript, right parenthesis pentru orice constantă pozitivă $a$a. Însă, din moment ce valoarea lui $\log_2 n$log, start base, 2, end base, n se mărește pe măsură ce $n$n se mărește, $\Theta(\log_2 n)$\Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis crește mai repede decât $\Theta(1)$\Theta, left parenthesis, 1, right parenthesis.

Următorul grafic compară creșterile pentru $1$1, $n$n și $\log_2 n$log, start base, 2, end base, 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:

Ține minte că funcția exponențială $a^n$a, start superscript, n, end superscript, unde $a > 1$a, is greater than, 1, crește mai repede decât orice funcție polinomială $n^b$n, start superscript, b, end superscript, unde $b$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ă a Khan Academy. Conținutul este licențiat CC-BY-NC-SA.