BitCell

E unul dintre subiectele pe care nu le-am priceput(pana acum,hopefully).
So, avem urmatorul cod :
1:

2:

Instructiunile nu trebuie sa fie neaparat la fel,dar totusi sa aiba acelasi numar de operatii.
Primul "algoritm" are complexitate O(n*n) iar al doilea O(n) ?
Daca da, de ce ? La cum le vad eu , cred ca vor rula in acelasi timp.
E cam ambiguu post-ul, sper sa intelegeti.

Al doilea algoritm are o complexitate de O(2n). Cu doua bucle imbricate (ca in primul exemplu) poti parcurge o matrice de NxN elemente. Cu doua bucle secventiale (ca in al doilea exemplu) poti parcurge doar doua linii (sau coloane) din respectiva matrice - hence, O(2n).

Oricum, in acest al doilea caz, complexitatea este, de fapt, O(n) - fiindca ne intereseaza rata de crestere a timpului de rulare (memoria ocupata, etc) al algoritmilor. Fiindca "2" este constant, rata de crestere este data de N => complexitatea este de O(n).

Bafta

P.S. Spuneai ca tu crezi ca vor rula in acelasi timp. E usor de demonstrat ca bucla imbricata (din primul exemplu) se va executa de NxN ori ... incearca sa aduni cu 1 o variabila C (contor ... sa zicem ) in FOR-ul care foloseste "j" - si afiseaza variabila C chiar inainte de a se termina programul. In al doilea exemplu, fiecare bucla se executa de N ori, adica N + N. Poti face acelasi test cu o variabila contor daca nu ma crezi pe cuvant

In primul cod pentru fiecare valoare luata de i, j-ul parcurge toate valorile de la 1 la n
deci pt i=1: j face n parcurgeri
pt i=2 j face n parcurgeri
pt i=3 j face n parcurgeri
..................
pt i=n j face n parcurgeri

deci j face n*n parcurgeri (in total) complexitatea fiind O(n*n) //reprezinta de cate ori se executa instructiunile
Daca ai avea 3 de for atunci complexitatea ar fi O(n*n*n)

In cel de-al doilea cod sunt doua foruri separate.
Primul face n parcurgeri iar cel de-al II-lea face tot n parcurgeri
Deci ambele fac 2*n parcurgeri. Complexitatea fiind O(2*n), insa acel 2 este o constanta si se face abstractie de el. Deci da, complexitatea celui de-al II-lea cod este O(n);

Deci daca ai o complexitate de forma O(x*n) unde x este un numar mic o poti scrie O(n).
Daca ai o complexitate O(n+x) unde x este un numar mic o poti scrie tot O(n)

Ex: O(n+12)=O(n)

Era un tutorial despre asta aici: http://www.bitcell.info/introducere-in-algoritmica-t107.html

Multumesc all, si pentru raspunsuri si pentru tutorial, acum am inteles ^_^.