Complessità computazionale

MPG

Utente Attivo
464
2
Ciao a tutti. Il prof ha iniziato a spiegare la complessità computazionale (sono in 4 superiore) vorrei chiedervi se c'è qualche manuale o dove posso cercare online per capire meglio l'argomento. Vi ringrazio.
 

Waveharp

Utente Èlite
6,240
3,228
CPU
Ryzen 5 3600 @ 4.2ghz 1.35v
Dissipatore
Custom Loop: wb cpu e gpu EK+HL gts 360 x2 P&P 9 ventole
Scheda Madre
Asus Prime X470 Pro
Hard Disk
Samsung 960 Evo + Samsung 850 Evo
RAM
16 gb G skill Trident NEO 3600mhz CL16
Scheda Video
Evga 1080TI Sc Black Gaming OC
Monitor
Acer Predator 27" 144hz 1440p IPS
Alimentatore
Evga 650W SuperNova G2
Case
Cooler Master H500M
Sistema Operativo
Win 10 Pro 64 bit

MPG

Utente Attivo
464
2
Ho capito su google ovvio che ho già cercato ma poichè ci sono miriadi di link, magari qualcuno di voi sa dirmi dove si trova qualcosa di esauriente e ben spiegato con esempi. Grazie.
 

DispatchCode

Utente Attivo
791
505
CPU
Intel i7 6700HQ, 2.60Ghz, 4 core 8 threads
Scheda Madre
Asustek
Hard Disk
Hitachi 7200 rpm, 1TB
RAM
16GB DDR4 (2 slot su 4)
Scheda Video
Nvidia Geforce GTX 960M, 4GB
Scheda Audio
Realtek
Internet
30Mbps/3Mbps con Eolo
Sistema Operativo
Windows 10 64bit
Di risorse ne trovi un sacco, alcune sono però piuttosto formali.
Guarda ad esempio qui:




Se hai domande in merito a qualcosa, chiedi.
 
  • Mi piace
Reactions: Moffetta88 e MPG

MPG

Utente Attivo
464
2
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
Post automaticamente unito:

In attesa di avere indicazioni vostre anche questi due:

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è???????
 
Ultima modifica:

DispatchCode

Utente Attivo
791
505
CPU
Intel i7 6700HQ, 2.60Ghz, 4 core 8 threads
Scheda Madre
Asustek
Hard Disk
Hitachi 7200 rpm, 1TB
RAM
16GB DDR4 (2 slot su 4)
Scheda Video
Nvidia Geforce GTX 960M, 4GB
Scheda Audio
Realtek
Internet
30Mbps/3Mbps con Eolo
Sistema Operativo
Windows 10 64bit
Inizio a risponderti ad alcuni... non mi è proprio tutto chiarissimo ciò che hai scritto, comunque. Mi aspettavo anche più approssimazioni senza contare le operazioni costanti.

Ad ogni modo:

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!!!!
2*n perchè all'interno del ciclo hai 2 assegnamenti, e li ripeti n volte. Quindi 2*n.

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è???????
Il costo di i=i+1 non può essere N in quanto l'operazione viene ripetuta sqrt n volte; quindi il costo effettivo è sqrt n * 1 (l'assegnamento).

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
La i non viene incrementata solo N volte, ma n*n volte, quindi n^2.
 
  • Mi piace
Reactions: MPG

MPG

Utente Attivo
464
2
Grazie tante veramente!
giusto per essere certo:
1) nella prima risposta i due assignamenti sono ovviamente
i=i+1
j=j*3+42

(scusa la banalità della domanda..)
2) nella terza dovrebbe essere cosi?:

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

Perchè non viene sempre 2n^2+2 o sbaglio ?


3) riesci a spiegarmi anche questo?
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....
 
Ultima modifica:

Entra

oppure Accedi utilizzando

Discussioni Simili

Hot del momento