Reprezinta doar cat de bine se comporta un algoritm. Ma gandesc la el ca fiind de fapt un fel de timp,durata ce are legatura cu loop-urile din cod (de obicei o sa vezi ca O-complexitatea apare doar la algoritmii cu for-uri sau while-uri).
Ex.: for(int i=0;i<n;i++)
for(int j=0;j<n;i++) a+=1
Comanda "a+=1" va fi executata de i*j ori ori n^2. Deci daca fiecare iteratie reprezinta o unitate de "timp-complexa" poti spune ca complexitatea e O(n^2).
Acesta a fost un loop in loop. In acest caz numarul maxim de iteratii al primului for e inmultit cu nr. maxim de iteratii de la al doilea loop(in cazul nostru n*n)
Insa cand sunt doua loop-uti unul dupa altul atunci aduni "complexitatile":
for(int i=0;i<n;i++) k+=1;
for(int j=0;j<n;j++) k+=45;
Aici comlpexitatea e O(2n).
Insa exista si loopuri sofisticate:
for(int i=0;i<n;i++)
for(int j=i;j<n;j++) x+=71;
Aici nu poti nimic altceva decat sa vezi de cate ori e executata comanda x+=71;
Cand i=0 atunci j va lua valori de la 0 pana la n(fara n). Deci de n ori.
....In final:n+(n-1)+(n-2)+...+[n-(n-2)]+[n-(n-1)]=1+2+...+n. Deci codul a fost executat de n*(n+1)/2 ori. Complexitatea O(n*(n+1)/2). Un lucru mai trebuie sa stii O(c*n)=O(n) (se duce constanta c) . Deci in cazul nostru O(n(n+1)/2)=O((1/2)*n*(n+1))=O(n*(n+1)) =O(n^2+n). Cand exista un astfel de caz n se duce deoarece e mai mic decat celalalt termen(n^2) ..deoarece "inainteaza" mai greu. Deci complexitatea va fi O(n^2)
Insa sunt si alte reguli.
