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

Notația asimptotică

Până acum am analizat căutarea liniară și căutarea binară, numărând câte încercări trebuie să facem pentru a găsi o valoare într-un șir. Ce ne dorim de fapt să știm este cât durează execuția acestor algoritmi. Așadar, ne interesează timpul, nu doar încercările. Timpii de execuție ai căutării liniare și ai căutării binare includ timpul necesar pentru a face presupuneri și pentru a le verifica, dar mai sunt câteva detalii de luat în considerare la acești algoritmi.
Timpul de execuție al unui algoritm depinde de cât timp îi trebuie unui calculator să ruleze liniile de cod ale algoritmului - iar asta depinde de viteza calculatorului, de limbajul de programare, de compilatorul care traduce programul din limbajul de programare în limbaj mașină (cel înțeles de calculator) și de alți factori.
Să studiem mai atent timpul de execuție al unui algoritm. Vom îmbina două idei. În primul rând, trebuie să aflăm care este durata algoritmului în funcție de dimensiunea datelor de intrare. Ideea aceasta are sens, nu-i așa? Deja am văzut că numărul maxim de presupuneri în căutarea liniară și în căutarea binară crește odată cu creșterea dimensiunii vectorului. Sau gândește-te, de exemplu, la un GPS. Dacă acesta ar cunoaște doar rețeaua de autostrăzi dintre orașe, nu și fiecare străduță, ar găsi rutele mai repede, corect? Așadar, privim timpul de execuție al unui algoritm ca pe o funcție de dimensiunea datelor sale de intrare.
În al doilea rând, trebuie să ne concentrăm pe viteza cu care crește o funcție odată cu dimensiunea datelor de intrare. Numim această viteză ordinul de creștere al timpului de execuție. Pentru a menține analiza la un nivel mai puțin complicat, trebuie să simplificăm funcția pentru a păstra doar părțile importante. De exemplu, să presupunem că un algoritm ce se execută pe un set de date de intrare de dimensiune n, folosește 6n2+100n+300 instrucțiuni în limbaj mașină. Termenul 6n2 crește sesizabil mai repede decât ceilalți doi (100n+300) pentru n suficient de mare (20 în acest caz). Iată un grafic ce ilustrează valorile pentru 6n2 și 100n+300 pentru n de la 0 la 100:
Spunem că timpul de execuție al acestui algoritm crește ca n2, renunțând la coeficientul 6 și la termenii 100n+300. Indiferent de coeficienții pe care îi folosim, dacă timpul de execuție este de forma an2+bn+c, pentru niște valori oarecare a>0, b, și c, atunci întotdeauna va exista o valoare a lui n pentru care an2 este mai mare decât bn+c, iar această diferență crește odată cu n. De exemplu, iată un grafic ce ilustrează valorile pentru 0.6n2 și 1000n+3000, în care am micșorat coeficientul lui n2 de 10 ori și am mărit celelalte două constante de 10 ori:
Valoarea lui n pentru care 0.6n2 este mai mare decât 1000n+3000 a crescut, dar întotdeauna va exista un astfel de punct de intersecție, indiferent de valoarea constantelor.
Renunțând la termenii mai puțin semnificativi și la coeficienții constanți, ne putem concentra pe partea principală a timpului de execuție al unui algoritm - ordinul său de creștere - fără a ne încurca în detalii care ne complică înțelegerea. Când renunțăm la coeficienții constanți și la termenii mai puțin semnificativi, folosim notația asimptotică. Vom vedea trei clase ale acestei notații: notația Θ, notația O și notația Ω.

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.