Conţinutul principal

Curs: Biblioteca de informatică > Unitatea 1

Lecția 3: Notația asimptotică

Notația Marele-θ (Marele-Theta)

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

var doLinearSearch = function(array, targetValue) {
  for (var guess = 0; guess < array.length; guess++) {
    if (array[guess] === targetValue) { 
        return guess;  // am găsit valoarea căutată!
    }
  }
  return -1;  // nu am găsit-o
};

Haide să notăm dimensiunea vectorului (array.length) cu

n

. Numărul maxim de execuții ale repetiției for este

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:

compară guess cu array.length
compară array[guess] cu targetValue
dacă este cazul, returnează valoarea lui guess
incrementează guess.

Fiecare dintre aceste operații necesită timp constant pentru a se executa. Dacă repetiția for se execută de

n

ori, atunci timpul pentru toate cele

n

iterații este

c_{1} \cdot n

, unde

c_{1}

este suma timpilor pentru calculele dintr-o singură iterație a repetiției. Nu putem spune cu exactitate care este valoarea lui

c_{1}

, 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}

, 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}

După cum am discutat, termenul constant

c_{1}

și termenul nesemnificativ

c_{2}

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

, dimensiunea vectorului. Notația pe care o folosim pentru acest timp de execuție este

Θ (n)

(litera grecească „theta”).

Când spunem că un timp de execuție este

Θ (n)

, spunem de fapt că odată ce

n

este suficient de mare, timpul de execuție este cel puțin

k_{1} \cdot n

și cel mult

k_{2} \cdot n

pentru niște constante oarecare

k_{1}

și

k_{2}

. Iată o ilustrație pentru

Θ (n)

Pentru valori mici ale lui

n

, nu ne interesează cum este timpul de execuție în raport cu

k_{1} \cdot n

k_{2} \cdot n

. Însă, odată ce

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

și

k_{2} \cdot n

. Atât timp cât aceste constante

k_{1}

și

k_{2}

există, spunem că timpul de execuție este

Θ (n)

Nu ne limităm doar la

n

atunci când lucrăm cu notația Θ. Putem folosi orice funcție, cum ar fi

n^{2}

n \log_{2} n

, practic orice altă funcție cu

n

. Iată cum poți privi un timp de execuție care este

Θ (f (n))

pentru o funcție

f (n)

Odată ce

n

este suficient de mare, timpul de execuție se află între

k_{1} \cdot f (n)

și

k_{2} \cdot f (n)

Î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

6 n^{2} + 100 n + 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

100 n + 300

și spui doar că timpul de execuție este

Θ (n^{2})

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

. 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ă de la Khan Academy. Conținutul este licențiat CC-BY-NC-SA.

Vrei să te alături conversației?

Conectare

Ordonare după:

Nici o postare încă.

Înțelegi engleza? Dă clic aici pentru a vedea mai multe discuții care au loc pe site-ul în limba engleză al Khan Academy.