Complexitate algoritmi

[•Slevy]

Salut ! Stie cineva un site bun in care se explica cum sa calculez complexitatea unui algoritm sau e cineva dragut sa imi explice cate ceva ?

[•sigrid]

In linii mari complexitatea timp se refera la cate operatii se efectueaza in timpul rularii unui program.
De exemplu daca ai un for pana la N, fiecare pas al for-ului reprezinta o operatie => vei avea complexitate timp O(N).
Constantele nu se iau in calcul => O(N) ruleaza la fel de repede ca O(2*N).
Daca programul efectueaza un numar descris de o functie exponentiala de instructiuni => complexitate exponentiala. Inversul functiei exponentiale este logaritmul => complexitate logaritmica.

Complexitatea memorie se refera la cata memorie se aloca in timpul rularii programului. De exemplu daca ai nevoie sa retii o matrice de N linii, M coloane complexitatea memorie va fi N*M.

Daca esti ok cu engleza, pe wikipedia gasesti un articol destul de ok (Analysis of algorithms).

[•Slevy]

Pentru numarul de operatii pe care le efectueaza algoritmul nu se foloseste T(n) ? Iar complexitatea  memorie cu ce se noteaza ?
Mersi pentru raspunsuri !