Notația Marele-θ (Marele-Theta)

Iată o implementare simplă a căutării liniare:

Haide să notăm dimensiunea vectorului (array.length) cu $n$n. Numărul maxim de execuții ale repetiției for este $n$n, iar acesta este cel mai nefavorabil caz și apare atunci când valoarea căutată nu se găsește în vector.

De fiecare dată când repetiția for se execută, trebuie să facă mai multe operații:

Fiecare dintre aceste operații necesită timp constant pentru a se executa. Dacă repetiția for se execută de $n$n ori, atunci timpul pentru toate cele $n$n iterații este $c_1 \cdot n$c, start subscript, 1, end subscript, dot, n, unde $c_1$c, start subscript, 1, end subscript este suma timpilor pentru calculele dintr-o singură iterație a repetiției. Nu putem spune cu exactitate care este valoarea lui $c_1$c, start subscript, 1, end subscript, deoarece ea depinde de viteza calculatorului, de limbajul de programare folosit, de compilatorul sau interpretorul care traduce programul sursă în cod executabil și de alți factori.

Acest cod face câteva operații suplimentare, pentru a pregăti repetiția for (inclusiv inițializarea lui guess cu 0) și eventual pentru a returna -1 la final. Să notăm timpul alocat acestor operații cu $c_2$c, start subscript, 2, end subscript, care este tot o constantă. Așadar, timpul total de execuție al căutării liniare în cazul cel mai nefavorabil este $c_1 \cdot n + c_2$c, start subscript, 1, end subscript, dot, n, plus, c, start subscript, 2, end subscript.

După cum am discutat, termenul constant $c_1$c, start subscript, 1, end subscript și termenul nesemnificativ $c_2$c, start subscript, 2, end subscript nu ne oferă informații despre ordinul de creștere al timpului de execuție. Important este că timpul de execuție în cazul cel mai nefavorabil al căutării liniare crește odată cu $n$n, dimensiunea vectorului. Notația pe care o folosim pentru acest timp de execuție este $\Theta(n)$\Theta, left parenthesis, n, right parenthesis (litera grecească „theta”).

Când spunem că un timp de execuție este $\Theta(n)$\Theta, left parenthesis, n, right parenthesis, spunem de fapt că odată ce $n$n este suficient de mare, timpul de execuție este cel puțin $k_1 \cdot n$k, start subscript, 1, end subscript, dot, n și cel mult $k_2 \cdot n$k, start subscript, 2, end subscript, dot, n pentru niște constante oarecare $k_1$k, start subscript, 1, end subscript și $k_2$k, start subscript, 2, end subscript. Iată o ilustrație pentru $\Theta(n)$\Theta, left parenthesis, n, right parenthesis:

Pentru valori mici ale lui $n$n, nu ne interesează cum este timpul de execuție în raport cu $k_1 \cdot n$k, start subscript, 1, end subscript, dot, n sau $k_2 \cdot n$k, start subscript, 2, end subscript, dot, n. Însă, odată ce $n$n este suficient de mare - se află pe linia punctată sau la dreapta sa - timpul de execuție trebuie încadrat între $k_1 \cdot n$k, start subscript, 1, end subscript, dot, n și $k_2 \cdot n$k, start subscript, 2, end subscript, dot, n. Atât timp cât aceste constante $k_1$k, start subscript, 1, end subscript și $k_2$k, start subscript, 2, end subscript există, spunem că timpul de execuție este $\Theta(n)$\Theta, left parenthesis, n, right parenthesis.

Nu ne limităm doar la $n$n atunci când lucrăm cu notația Θ. Putem folosi orice funcție, cum ar fi $n^2$n, squared, $n \log_2 n$n, log, start base, 2, end base, n, practic orice altă funcție cu $n$n. Iată cum poți privi un timp de execuție care este $\Theta(f(n))$\Theta, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis pentru o funcție $f(n)$f, left parenthesis, n, right parenthesis:

Odată ce $n$n este suficient de mare, timpul de execuție se află între $k_1 \cdot f(n)$k, start subscript, 1, end subscript, dot, f, left parenthesis, n, right parenthesis și $k_2 \cdot f(n)$k, start subscript, 2, end subscript, dot, f, left parenthesis, n, right parenthesis.

În practică, renunțăm pur și simplu la termenii constanți și la cei nesemnificativi. Un alt avantaj al notației Θ este că nu trebuie să ne facem griji în legătură cu ce unități de măsură folosim pentru timp. De exemplu, să spunem că tu calculezi timpul de execuție $6n^2 + 100n + 300$6, n, squared, plus, 100, n, plus, 300 în microsecunde. Sau poate că îl calculezi în milisecunde. Când utilizezi notația Θ, nu trebuie să specifici unitatea de măsură. De asemenea, renunți la constanta 6 și la termenii $100n + 300$100, n, plus, 300 și spui doar că timpul de execuție este $\Theta(n^2)$\Theta, left parenthesis, n, squared, right parenthesis.

Când folosim notația Θ, spunem că facem o aproximare asimptotică a timpului de execuție. Aproximarea este „asimptotică” deoarece este relevantă doar pentru valori mari ale lui $n$n. O numim „aproximare” pentru că încadrăm timpul de execuție între doi termeni constanți, unul mai mare și unul mai mic.

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.