Conţinutul principal
Biblioteca de informatică
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 ( . Numărul maxim de execuții ale repetiției for este , iar acesta este cel mai nefavorabil caz și apare atunci când valoarea căutată nu se găsește în vector.
array.length
) cu De fiecare dată când repetiția for se execută, trebuie să facă mai multe operații:
- compară
guess
cuarray.length
- compară
array[guess]
cutargetValue
- 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 ori, atunci timpul pentru toate cele iterații este , unde este suma timpilor pentru calculele dintr-o singură iterație a repetiției. Nu putem spune cu exactitate care este valoarea lui , 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 , care este tot o constantă. Așadar, timpul total de execuție al căutării liniare în cazul cel mai nefavorabil este .
guess
cu 0) și eventual pentru a returna -1
la final. Să notăm timpul alocat acestor operații cu După cum am discutat, termenul constant și termenul nesemnificativ 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 , dimensiunea vectorului. Notația pe care o folosim pentru acest timp de execuție este (litera grecească „theta”).
Când spunem că un timp de execuție este , spunem de fapt că odată ce este suficient de mare, timpul de execuție este cel puțin și cel mult pentru niște constante oarecare și . Iată o ilustrație pentru :
Pentru valori mici ale lui , nu ne interesează cum este timpul de execuție în raport cu sau . Însă, odată ce este suficient de mare - se află pe linia punctată sau la dreapta sa - timpul de execuție trebuie încadrat între și . Atât timp cât aceste constante și există, spunem că timpul de execuție este .
Nu ne limităm doar la atunci când lucrăm cu notația Θ. Putem folosi orice funcție, cum ar fi , , practic orice altă funcție cu . Iată cum poți privi un timp de execuție care este pentru o funcție :
Odată ce este suficient de mare, timpul de execuție se află între și .
Î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 î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 și spui doar că timpul de execuție este .
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 . 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?
Nici o postare încă.