Complessità computazionale

[MPG]

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.

 

[Utente cancellato 368991]

Qui

 

[MPG]

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]

Di risorse ne trovi un sacco, alcune sono però piuttosto formali.
Guarda ad esempio qui:

Complexity

Time and Space Complexity Tutorials & Notes | Basic Programming | HackerEarth

Detailed tutorial on Time and Space Complexity to improve your understanding of Basic Programming. Also try practice problems to test & improve your skill level.

www.hackerearth.com

Analysis of Algorithms | Big-O analysis - GeeksforGeeks

A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.

www.geeksforgeeks.org

Se hai domande in merito a qualcosa, chiedi.

 

[MPG]

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 unito automaticamente: 1 Febbraio 2020

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è???????

 

[DispatchCode]

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.

 

[MPG]

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....