Complexitate în timp

În informatică, complexitatea în timp a unui algoritm exprimă măsura timpului cât durează rularea algoritmului, ca funcție de lungimea șirului^⁠(d) ce reprezintă datele de intrare.^[1]^:226 Complexitatea în timp a unui algoritm este exprimată cel mai adesea folosind notația Big O, care exclude coeficienții și termenii de grad inferior. Când este exprimată astfel, se spune că complexitatea în timp este exprimată asimptotic, adică atunci când dimensiunea intrării tinde spre infinit. De exemplu, dacă durata de timp necesară unui algoritm pentru a rula pe intrări de dimensiune n este cel mult 5n³ + 3n pentru orice n (mai mare decât un n₀), complexitatea asimptotică în timp este O(n³).

Complexitatea în timp este frecvent estimată prin numărarea operațiilor elementare efectuate de algoritm, unde o operație are o durată fixă. Astfel, timpul de rulare diferă de numărul de operații elementare cel mult printr-un factor constant.

Deoarece performanța unui algoritm timp poate varia cu diferite intrări de aceeași mărime, se utilizează frecvent complexitatea în timp în cel mai rău caz, notată cu T(n), valoare definită ca fiind cantitatea maximă de timp consumată dintre toate intrările de dimensiune n. Mai puțin frecvent, și, de obicei, specificată în mod explicit, este măsura complexității în cazul mediu. Complexitățile în timp sunt clasificate în funcție de natura funcției T(n). De exemplu, un algoritm cu T(n) = O(n) se numește algoritm în timp liniar, iar un algoritm cu T(n) = O(kⁿ) pentru o constantă k>1 este numit algoritm în timp exponențial.

Tabel de complexități în timp frecvente

Următorul tabel rezumă unele clase de complexități în timp întâlnite frecvent. În tabel, poly(x) = x^O(1), adică polinomial în x.

Nume	Clasă de complexitate	Timp de rulare (T(n))	Exemple de timpi de rulare	Exemple de algoritmi
timp constant		O(1)	10	Determinarea dacă un număr întreg (reprezentat în binar) este par sau impar
timp invers Ackermann^⁠(d)		O(α(n))		Timp amortizat^⁠(d) pe operație folosind structuri de date cu mulțimi disjuncte^⁠(d)
timp logaritmic iterat		O(log* n)		Colorarea distribuită a ciclurilor
log-logaritmic		O(log log n)		Timp amortizat pe operație când se folosește o coadă cu priorități^⁠(d) mărginită^[2]
timp logaritmic	DLOGTIME^⁠(d)	O(log n)	log n, log(n²)	Căutarea binară
timp polilogaritmic		poly(log n)	(log n)²
putere fracționară		$O (n c)$ unde $0 < c < 1$	n^1/2, n^2/3	Căutarea într-un arbore kd^⁠(d)
timp liniar		O(n)	n	Găsirea celui mai mic sau a celui mai mare element dintr-un tablou^⁠(d) nesortat
timp "n log star n"		O(n log* n)		Algoritmul lui Seidel^⁠(d) de triangulare a poligonului.
timp cvasiliniar		O(n log n)	n log n, log n!	Cea mai rapidă sortare prin comparație^⁠(d) posibilă; transformata Fourier rapidă^⁠(d).
timp pătratic		O(n²)	n²	Bubble sort^⁠(d); Insertion sort^⁠(d); convoluția directă^⁠(d)
timp cubic		O(n³)	n³	Înmulțirea naivă a două matrice n×n. Calculul corelării parțiale^⁠(d).
timp polinomial	P	2^O(log n) = poly(n)	n, n log n, n¹⁰	Algoritmul lui Karmarkar^⁠(d) pentru programare liniară; testul de primalitate AKS^⁠(d)
timp cvasipolinomial	QP	2^poly(log n)	n^log log n, n^log n	Cel mai bine cunoscut algoritm de aproximare^⁠(d) O(log² n) pentru problema arborelui Steiner^⁠(d) orientată.
timp subexponențial (prima definiție)	SUBEXP	O(2^{n^ε}) oricare ar fi ε > 0	O(2^{log n^{log log n}})	Presupunând drept adevărate conjecturile de teoria complexității, BPP^⁠(d) este inclusă în SUBEXP.^[3]
timp subexponențial (a doua definiție)		2^o(n)	2^{n^1/3}	Cel mai cunoscut algoritm de factorizarea întregilor și de izomorfism de grafuri^⁠(d)
timp exponențial (cu exponent liniar)	E^⁠(d)	2^O(n)	1.1ⁿ, 10ⁿ	Rezolvarea problemei comis-voiajorului cu programare dinamică
timp exponențial	EXPTIME^⁠(d)	2^poly(n)	2ⁿ, 2^n²	Rezolvarea înmulțirilor în lanț ale matricilor^⁠(d) prin căutare cu forța brută^⁠(d)
timp factorial		O(n!)	n!	Rezolvarea problemei comis-voiajorului prin căutare cu forța brută^⁠(d)
timp dublu exponențial	2-EXPTIME^⁠(d)	2^{2^poly(n)}	2^2ⁿ	Decizia privind valoarea de adevăr a unei afirmații din aritmetica Presburger^⁠(d)

Timp constant

Se spune despre un algoritm că este în timp constant (sau timp O(1)) dacă valoarea lui T(n) este delimitată de o valoare care nu depinde de mărimea datelor de intrare. De exemplu, accesarea unui singur element într-un tablou^⁠(d) are nevoie de timp constant întrucât trebuie să fie efectuată o singură operațiune pentru a-l localiza. La fel și găsirea valorii minime într-un tablou sortat în ordine crescătoare – este primul element. Cu toate acestea, găsirea valorii minime într-un tablou neordonat nu este constantă de timp, întrucât este nevoie de o parcurgere a fiecărui element din tablou, în scopul de a determina valoarea minimă. Prin urmare, aceasta este o operațiune în timp liniar, care durează O(n). Dacă numărul de elemente este cunoscut în avans și nu se schimbă, cu toate acestea, un astfel de algoritm poate fi considerat a rula în timp constant.

În ciuda denumirii de „timp constant”, timpul de rulare nu trebuie să fie independent de dimensiunea problemei, ci o limită superioară a timpului de rulare trebuie să fie delimitată independent de dimensiunea problemei. De exemplu, taskul de a „schimba valorile a și b dacă este necesar, astfel încât a≤b” este considerat a rula în timp constant, chiar dacă durata efectivă poate depinde dacă este sau nu este deja adevărat că a ≤ b. Cu toate acestea, există unele constante t astfel încât timpul necesar este întotdeauna cel mult t.

Iată câteva exemple fragmente de cod care se execută în timp constant:

int index = 5;
int item = lista[index];
if (condiție adevărată) then
 efectuează operațiunii care se execută în timp constant
else
 efectuează alte operațiuni care se execută în timp constant
for i = 1 to 100
 for j = 1 to 200
 efectuează operațiunii care se execută în timp constant

Dacă T(n) este O(orice valoare constantă), aceasta este echivalentă cu și enunțată în notație standard, T(n) = O(1).

Se spune că un algoritm este în timp logaritmic dacă T(n) = O(log n). Ca urmare a utilizării sistemului de numerație binar de către calculatoare, logaritmul este frecvent în bază 2 (log₂ n, uneori scris lg n). Cu toate acestea, schimbarea bazei^⁠(d) pentru logaritmi, log_a n și log_b n diferă doar printr-o constantă multiplicativă, care în notație Big-O este eliminată; astfel că O(log n) este o notație standard pentru algoritmii în timp logaritmic, indiferent de baza logaritmului.

Timp logaritmic

Algoritmii care au durata de execuție în timp logaritmic se întâlnesc de obicei în operații pe arbori binari sau atunci când se utilizează căutarea binară.

Un algoritm O(log n) este considerat extrem de eficient, deoarece numărul de operațiuni pe instanță necesar pentru a finaliza rularea scade la fiecare instanță.

Un exemplu foarte simplu de acest tip este un algoritmul care taie un șir în jumătate, apoi taie jumătatea din dreapta în jumătate, și așa mai departe. El va dura O(log n) (n fiind lungimea șirului) deoarece șirul se taie în jumătate înainte de fiecare tipărire (presupunând că console.log și str.substring rulează în timp constant).

Aceasta înseamnă că, pentru a crește numărul de tipăriri cu 1, trebuie dublată lungimea șirului.

// Function to recursively print the right half of a string
var right = function(str){
    var length = str.length;
    
    // Helper function
    var help = function(index){
        
        // Recursive Case: Print right half
        if(index < length){
          
            // Prints characters from index until the end of the array
            console.log(str.substring(index, length));
            
            // Recursive Call: call help on right half
            help(Math.ceil((length + index)/2));
        }
        
        // Base Case: Do Nothing
    }
    help(0);
}

Timp polilogaritmic

Un algoritm este considerat a fi în timp polilogaritmic dacă T(n) = O((log n)^k), pentru un k constant. De exemplu, ordonarea lanțului de matrice poate fi rezolvată în timp polilogaritmic pe o mașină cu acces aleator paralel.

Timp subliniar

Se spune că un algoritm rulează în timp subliniar dacă T(n) = o(n). În particular, aici sunt incluși algoritmii cu complexitățile definite mai sus, precum și alții cum ar fi căutarea lui Grover^⁠(d) de complexitate O(n^½).

Algoritmii tipici care sunt exacți și totuși rulează în timp subliniar folosesc prelucrări paralele (așa cum face algoritmul NC₁ de calcul al determinantului matricei), prelucrări neclasice^⁠(d) (de exemplu, căutarea lui Grover), sau li se garantează unele presupuneri despre structura datelor de intrare (cum ar fi căutarea binară și mulți algoritmi de mentenanță a arborilor, care rulează în timp logaritmic). Limbajele formale însă, așa cum este mulțimea tuturor șirurilor care au un bit de 1 pe poziția indicată de primii log(n) biți ai șirului, ar putea depinde de toți biții intrării, dar tot ar putea fi calculați în timp subliniar.

Termenul specific algoritm în timp subliniar este de regulă rezervat algoritmilor diferiți de cei de mai sus prin aceea că sunt rulați peste modele seriale clasice de mașină și nu au dreptul la prezumții despre datele de intrare.^[4] Ei pot însă să fie randomizați^⁠(d), și chia trebuie pentru orice task netrivial.

Cum un astfel de algoritm trebuie să dea un răspuns fără a-și citi datele de intrare în întregime, detaliile lui depind masiv de accesul permis asupra intrării. De regulă, pentru o intrare reprezentată de un șir binar b₁,...,b_k se presupune că algoritmul poate cere și primi într-un timp O(1) valoarea lui b_i oricare ar fi i.

Algoritmii în timpi subliniari sunt de regulă randomizați și furnizează doar soluți aproximative^⁠(d). De fapt, se poate demonstra ușor că nu este decidabilă proprietatea unui șir binar de a avea doar zerouri (și niciun 1) printr-un algoritm neaproximativ în timp subliniar. Algoritmii în timpi subliniari apar natural în cercetarea testării proprietăților^⁠(d).

Referințe

^ Eroare la citare: Etichetă <ref> invalidă; niciun text nu a fost furnizat pentru referințele numite Sipser
^ Mehlhorn, Kurt; Naher, Stefan (1990). „Bounded ordered dictionaries in O(log log N) time and O(n) space”. Information Processing Letters. 35 (4): 183–189. doi:10.1016/0020-0190(90)90022-P.
^ Eroare la citare: Etichetă <ref> invalidă; niciun text nu a fost furnizat pentru referințele numite bpp
^ Kumar, Ravi; Rubinfeld, Ronitt (2003). „Sublinear time algorithms” (PDF). SIGACT News. 34 (4): 57–67. doi:10.1145/954092.954103.

[Sipser-1] Eroare la citare: Etichetă <ref> invalidă; niciun text nu a fost furnizat pentru referințele numite Sipser

[2] Mehlhorn, Kurt; Naher, Stefan (1990). „Bounded ordered dictionaries in O(log log N) time and O(n) space”. Information Processing Letters. 35 (4): 183–189. doi:10.1016/0020-0190(90)90022-P.

[bpp-3] Eroare la citare: Etichetă <ref> invalidă; niciun text nu a fost furnizat pentru referințele numite bpp

[4] Kumar, Ravi; Rubinfeld, Ronitt (2003). „Sublinear time algorithms” (PDF). SIGACT News. 34 (4): 57–67. doi:10.1145/954092.954103.

[1]

[2]

[3]

[4]