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$n, folosește $6n^2 + 100n + 300$6, n, squared, plus, 100, n, plus, 300 instrucțiuni în limbaj mașină. Termenul $6n^2$6, n, squared crește sesizabil mai repede decât ceilalți doi ($100 n + 300$100, n, plus, 300) pentru $n$n suficient de mare (20 în acest caz). Iată un grafic ce ilustrează valorile pentru $6n^2$6, n, squared și $100n + 300$100, n, plus, 300 pentru $n$n de la 0 la 100:

Spunem că timpul de execuție al acestui algoritm crește ca $n^2$n, squared, renunțând la coeficientul 6 și la termenii $100n + 300$100, n, plus, 300. Indiferent de coeficienții pe care îi folosim, dacă timpul de execuție este de forma $an^2 + bn + c$a, n, squared, plus, b, n, plus, c, pentru niște valori oarecare $a > 0$a, is greater than, 0, $b$b, și $c$c, atunci întotdeauna va exista o valoare a lui $n$n pentru care $an^2$a, n, squared este mai mare decât $bn + c$b, n, plus, c, iar această diferență crește odată cu $n$n. De exemplu, iată un grafic ce ilustrează valorile pentru $0.6n^2$0, point, 6, n, squared și $1000n + 3000$1000, n, plus, 3000, în care am micșorat coeficientul lui $n^2$n, squared de 10 ori și am mărit celelalte două constante de 10 ori:

Valoarea lui $n$n pentru care $0.6n^2$0, point, 6, n, squared este mai mare decât $1000n + 3000$1000, n, plus, 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 $\Theta$\Theta, notația O și notația $\Omega$\Omega.

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.