Question

Buna ziua ! Vreau sa va rog frumos deoarece am admiterea la facultate si eu la scoala nu ne-a invatat profesoara!CUm se calculeaza complexitatea algoritmilor in functie de timp si de memorie stiu ca era ceva cu log si polinom de gradul 3! ma ajutati va rog

Answer 1

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.