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
Răspunsuri la întrebare
Răspuns de
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.
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.
GeorgeDINFO:
Bun si daca este O(n^2) inseamna ca este log in baza 2 din n^2? sauu ce mai trebuie calculat si la complexitatea in functie de memorie?
Alte întrebări interesante
Matematică,
9 ani în urmă
Matematică,
9 ani în urmă
Matematică,
9 ani în urmă
Matematică,
9 ani în urmă
Limba română,
9 ani în urmă
Limba română,
9 ani în urmă