infoarena

Ma uit peste forumul arhivei de probleme si vad la fiecare topic : "Problema se rezolva folosind o complexitate O(...) " . Cam banuiesc eu la ce se refera complexitatea respectiva , dar cum se calculeaza ? .. va rog help  :D

In functie de structurile repetitive... Daca ai un for care merge de la 1 la n, instructiunile din cadrul for-urului se repeta de n ori, si complexitatea e liniara sau O(n)...
Daca ai 2 structuri repetitive imbricate ceva in genul:

for(i = 1; i <= n; ++i)
      for(j = 1; j <= n; ++j)
               {
                    instr1;
                    instr2;
               }

Complexitatea este O(n^2).... La fel pentru 3 structuri, 4 etc

O chestie ce mi se pare si mie ciudata este ca daca ai 3 structuri repetive fiecare de complexitate O(n), complexitatea finala este O(n) + O(n) + O(n).... care nu va fi egala cu 3*O(n), ci O(n) :P

Later edit: Daca nu contine structuri repetitive complexitatea va fi O(1).

Mersi pt raspunsul rapid :D, dar am vazut tot felu de complexitati ciudate cu logaritmi si chestii de gen .. alea la ce se refera ? ???

Daca ai facut la (for-urile precendente:D)o optimizare:

for(i = 1; i <= n  &&  ok; ++i)
      for(j = 1; j <= n; ++j)
            {
                 if(conditie)
                    ok = 0;
                 instr1;
            }

La un anumit pas, ok poate sa devina 0... si instructiunile nu se vor executa de n*n, ci de n*logn...... Asta e explicatia gasita de mine si un exemplu :)

spre ex daca ai :

for ( i = 1 , i <= n; i++ )
{
      for ( j = 1; j*j <= n; j++ )
      {
          // ...
      }
}

acesta are complexitatea O(n*logn);

Asta nu ii O(n*sqrt(n))??  :eyebrow:

asta seamana mai degraba cu O(n*radical(n))

si la exemplul lui Andrei, de unde stim noi ca conditia respectiva se va rula vreodata , de ex, daca nu se ruleaza niciodata tot (n^2) ii

Gasesti aici ceva documentatie:
http://en.wikipedia.org/wiki/Computational_complexity_theory

depinde de conditie. Nu e tocmai un exemplu f bun. uite un exemplu bun in n log n

Gasesti si in Cormen o gramada de chestii despre toate chestiile astea care exprima numarul de pasi, de operatii, etc. (mai pe la inceput parca  :-k )

M-ati mai lamurit putin. Am cautat si eu pe wikipedia dar mare lucru n-am inteles :P Mai is inca cateva chestii care mi-s neclare dar o sa le prind din zbor :P mersi :thumbup:

Sau in Tudor Sorin  de a X-a exista un capitol special despre exprimarea complexitatii algoritmilor..

 :thumbup:

Asta-i manual ? .. mentionez ca din clasa a 9-a si pana acum(clasa a 12-a) n-am avut nici un manual la info :P

Se gasesc in librarii..... :thumbup:

Scuze asta ii n*radical(n) , my bad  :'(

Poti sa faci comanda la editura ls-format.
email: [email protected]
web: www.ls-infomat.ro

( Numai ca din cate stiu se pot face comenzi de minim 10 bucati )

Daca mai convinge inca 9 oameni  :banana: .....

 :D
 :peacefingers:

Ideea e cu complexitatea e ca e aproximeaza numarul mediu de operatii pe care le poate efectua algoritmul tau, nu numarul exact de operatii pe care le efectueaza.
Pentru complexitati exista factori constanti ( care nu au nici o legatura cu variabile din problema), de exemplu un algoritm de genul:


este liniar, adica O(N), cu toate ca numarul de operatii este 81N. In plus, se pastreaza cea mai mare  putere din polinomul care descrie algoritmul. De exemplu:


are complexitatea O(N^2), nu O(N + N^2) - se pastreaza deci doar factorul dominant. Se mai poate scrie deci O(N) + O(N^2) = O(N^2) ( conceptual numarul medii de operatii pe care le va efectua programul, nu inseamna neaparat ca numarul de operatii este exact N^2 )

In legatura cu complexitatea logaritmica, cel mai cunoscut este cautarea binara. Ai intervalul [1, N] si il tot injumatatesti. Deci il poti injumatati de K ori maxim, unde 2^K <= N, si cum K = logN, complexitatea unui astfel de algoritm e O(log N). Daca repeti de N ori acest procedeu, obtii de exemplu: O(N) * O(logN) = O(N * log N). Sper ca ti-ai format macar niste idei :wink:

Mersi tuturor pentru raspuns  :D... Mi s-a mai clarificat acuma cum sta treaba cu complexitatea, am cautat pe wiki si am gasit pana la urma aici: http://en.wikipedia.org/wiki/Big_O_notation#Common_orders_of_functions ceva care sa explice pt fiecare tip d complexitate ce algoritm i se potriveste. (asta in cazul in care mai exista dinastia ca mine care nu inteleg O-ul ala  :-' )

Un articol destul de complet despre complexitate si cum se calculeaza, format din 2 parti:

http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=complexity1
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=complexity2

Partea a 2a prezinta si modalitati de calculare a complexitatii pentru algoritmi recursivi

Vezi sa nu te incurci cu modaliatetea asta de gandire. Nu e bine sa cauti ce algoritm are complexitatea X; mai bine invati pentru un algoritm cum sa ii calculezi complexitatea.
Dar oricum, iti trebuie putine cunostiinte matematice ca sa intelegi mai bine cum sa calculezi aceste complexitati..

Articolul de pe TopCoder este destul de bun, insa o mica precizare - in tabelul respectiv cu complexitatiile si Nul maxim ce intra in timp, acel tabel este pentru calculatorul de la TopCoder, pentru un timp maxim de executie de 8 secunde. Majoritatea problemelor ce 0.1s; astfel O(N) are N maxim 1 milion, O(N²) cam 1000 samd.
Totodata conteaza mult ce fel de operatii faci si cat de multe faci. Adica un program cu 100 de foruri de O(N) s-ar putea sa mearga mai greu decat un program in O(N logN), desi dupa analiza complexitatii ar trebui sa mearga mai repede. Ce vreau sa iti zic este ca O(N) este mai rapid decat O(N logN) pentru valori infinit de mari ale lui N. Acel 100 este ceea ce o sa mai intalnesti in discutii ca fiind 'constanta'. Un alt exemplu de diferenta de 'constanta' - ai un singur for in O(N), dar care face operatii matematice complexe (radical, logaritm, arctangen..) pe cand acel O(N logN) sa faca doar niste simple adunari. Pentru valori mici ale lui N, O(N logN) va merge mai rapid.

Ca sa iti fie mai usor sa intelegi toate astea iti trebuie exercitiu; incearca ca la fiecare program pe care il scrii sa incerci sa ii analizezi complexitatea. O parcurgere in latime ce complexitate are? Un program care incearca toate solutiile posibile (backtracking de exemplu) ce complexitate are? E recomandat oricum sa intelegi teoria pentru a putea pune in practica asta :)