Pages: [1]   Go Down
Print
Author Topic: Complessità asintotica  (Read 912 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Alex_47
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 409


The spiral's King


« on: 06-06-2009, 17:21:30 »

Ragazzi secondo voi qual'è la complessità asintotica di questo algoritmo?

Code:
for(i = 2; i < n; i++)
   for(j = 2; j < n; j++)
       for(k= i - 2; k < i; k++)
            System.out.println(k);


secondo me n^2
Logged
ottobit
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 186


!nope!


« Reply #1 on: 06-06-2009, 17:35:43 »

Code:
for(i = 2; i < n; i++)
   for(j = 2; j < n; j++)
       for(k= i - 2; k < i; k++)
            System.out.println(k);
il primo ciclo lo esegue n-1 volte.
il secondo ciclo lo esegue n-1 volte.
il terzo ciclo lo esegue k volte,con k = i-2 ---> quindi sempre 2 volte!

Secondo me la complessità qui è ---> 2*n^2 ---> O(n^2)!
Poi non so se è giusto...
Logged
LtWorf
Forumista Esperto
****
Offline Offline

Posts: 1.079

Ogni cosa da me scritta è da intendersi come opinione personale e non come dato di fatto. Anche le eventuali dimostrazioni matematiche da me scritte saranno opinioni personali e quindi dovranno venire dimostrate da una terza parte di fiducia


WWW
« Reply #2 on: 06-06-2009, 22:38:34 »

Si mi pare corretto...
Logged

There are some OO programming languages. I will create the first -_-' language.

LtWorf
Pages: [1]   Go Up
Print
Jump to: