Aiuto calcolo complessità in numero di passi base

Messaggioda mpg » 01/02/2020, 14:28

Scusate la materia è un po' ostica abbiamo iniziato cosi (calcolo complessità in numero passi base)':

i=0
while (i<n)
I++


assegnato 1 a i=0 (assignamento esterno)
n+1 a i<n (numero di test)
n*1 a i++ (assignamento interno)
Passi base= 2n+2


Passando a questo
int i=0; j=0; 1+1
for int h=2, h<=h+1; h++) 1+(n+1) +n
{
while (i<n+2) n+2
{cout >>i>>endl; 1
i++; 1
}
j++, n++; n--; 1+1+1
}

dovrebbe venire (non pero' secondo i miei conti)
2+1+ (n+1)+n+[n+3+(n+2)(1+1)+1+1+1]
non capisco l'n+3 da dove viene....


infine questo: (pongo ad esempio n=2)

i=1; 1
while (i<n*n+1) n+3
{
i++ n+2



il risultato dovrebbe venire 2n^2+2 a me viene 1+n+3+n+2 =2n+6
*************
esercizio con
i=0
while (i<n)
{ i=i+1
j=j*3+42
}



assegnato 1 a i=0
n+1 a i<n
2*n come assegnamenti interni: questo non lo capisco!!!!


Infine

i=0
while (i*1<n)
i=i+1


abbiamo
1 (i=0)
√ n+1 (i*i<n) in effetti ad esempio per n=9 il ciclo è effettuato 3 volte= √ 9)
poi è assegnato √ n a i=i+1 perchè???????
mpg
Junior Member
Junior Member
 
Messaggio: 264 di 288
Iscritto il: 28/11/2017, 09:35

Re: Aiuto calcolo complessità in numero di passi base

Messaggioda apatriarca » 04/02/2020, 02:05

Nel secondo esercizio credo che consideri l'operazione h + 1 all'interno del test come operazione aggiuntiva a quelle che hai scritto e lo stesso per il n + 2 nel while interno.

Nel terzo esercizio il ciclo viene eseguito n * n volte. Il tuo calcolo è quindi certamente sbagliato.

Nel quarto hai 2 operazioni svolte n volte. Cosa non capisci?

Continuo a non capire il tuo dubbio, quella operazione viene certamente svolta un numero di volte pari a \(\sqrt{9} \).
apatriarca
Moderatore
Moderatore
 
Messaggio: 5357 di 5389
Iscritto il: 08/12/2008, 20:37
Località: Londra


Torna a Informatica

Chi c’è in linea

Visitano il forum: Nessuno e 6 ospiti