Aiuto calcolo complessità in numero di passi base

di Anonimizzato25685 il
3 risposte
/
Anonimizzato25685
Utente anonimizzato
Scusate sono in 4 superiore e questo argomento è un po' ostico per me,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)
v n+1 (i*i<n) in effetti ad esempio per n=9 il ciclo è effettuato 3 volte= v 9)
poi è assegnato v n a i=i+1 perchè???????

3 Risposte

  • Avatar di Weierstrass
    Utente Famoso
    Iscritto da
    feb, 2019
    Messaggi
    2221
    
for(int h=2, h<=h+1; h++)
    Questo dà infinito perché h non lo cambi mai dentro il ciclo. Sicuro di aver scritto giusto?
    
i=1; 
while (i<n*n+1) 
 i++;
    Questo dipende molto dal compilatore: se è un compilatore intelligente farà 
    
i=1;  // 1
k = n*n; // 1
k += 1; // 1
while( // n^2 * (...
    i<k   // ... 1 + ...
) 
 i++;   // ... 1)
    Quindi 1+1+1+n^2*(1+1) = 2n^2+3
    EDIT : a questo totale sottrai - 1 perché al passaggio finale non viene eseguito i++

    Ma comunque l'errore grosso era non aver fatto la moltiplicazione n^2*(istruzioni interne). n^2 è perché i inizia da 1, altrimenti sarebbe stato n^2+1
  • /
    Anonimizzato25685
    Utente anonimizzato
    Scusate io ho solo chiesto di avere spiegazione dei vari passi, Weirstass non capisco bene quello che mi hai detto, io non uso compilatori sono sono degli esercizi per capire questo argomento e ho dei dubbi e vorrei se possibili chiarimenti in quello che postato.
    Ho troavato anch'io qualcosa in giro ma forse non ci arrivo abbastanza....
Devi accedere o registrarti per scrivere nel forum
3 risposte