infoarena

infoarena - concursuri, probleme, evaluator, articole => Informatica => Subiect creat de: Simionescu Andrei din August 24, 2008, 21:57:27

Titlul: Intrebare
Scris de: Simionescu Andrei din August 24, 2008, 21:57:27

Ce complexitate are un program care se bazeaza pe urmatorul cod?

Cod:

[...]
for(i=1;i<=n-2;++i)
   for(j=i+1;j<n;++j)
      for(k=j+1;k<=n;++k)
         ana_are_mere++;
[...]

Titlul: RÄƒspuns: Intrebare
Scris de: Andrei Grigorean din August 24, 2008, 22:10:41

O(N^3)

Titlul: RÄƒspuns: Intrebare
Scris de: Simionescu Andrei din August 25, 2008, 10:39:36

da, stiu ca asa se aproximeaza, pe mine ma interesa de fapt exact cate operatii face, insa intrebarea era triviala, am gasit dupa 1 minut raspunsul si forma generala

Titlul: RÄƒspuns: Intrebare
Scris de: Andrei Grigorean din August 25, 2008, 11:54:31

Pai ai intrebat ce complexitate are, nu cate operatii face.

Numarul de incrementari ale variabilei ana_are_mere este aproximativ N^3/6.