Calcolo complessità algoritmo

Messaggioda Nepler265 » 07/12/2019, 13:18

salve ragazzi ho questo algoritmo ...


Codice:
procedure Esempio 2 (n : integer ) ; int k:=0; while (k ≤ n) { for ( int j = 1; j ≤ 3k ; j++) {t++}; for ( int r = 1; r ≤ k; r++) for ( int s = 1; s ≤ k; s++) A[ r , s ]:= s ; k++; }


Durante lo svolgimento si fanno i seguenti calcoli....



Immagine


Quello che non capisco è come e perchè vengono trasformate le sommatorie ...ad esempio quella che va da j=1 a 3^k diventa O(3^k) o le altre due che da r/s=1 a k danno O(k^2) e anche il penultimo passaggio dove la sommatoria che va da k=0 a n di : O(3^k)+O(k^2)=O(3^n)+O(n^3)
Qualcuno potrebbe cortesemente spiegarmelo ?
Nepler265
Starting Member
Starting Member
 
Messaggio: 14 di 25
Iscritto il: 18/09/2019, 11:05

Re: Calcolo complessità algoritmo

Messaggioda probid » 07/12/2019, 15:36

Quell'esercizio mi ricorda qualcosa... studi a Perugia? :-)
Comunque guardati l'appendice del Cormen relativa alle sommatorie, trovi tutto lì.

$\sum_{j=1}^{3^k} O(1) = O(\sum_{j=1}^{3^k} 1)$ (linearità) $ = O(\underbrace{1 + ... + 1}_{3^k \text{ volte}}) = O(3^k)$
stesso ragionamento per le altre
$\sum_{k=0}^{n} 3^k$ è una serie geometrica
$\sum_{k=0}^{n} k^2$ è anch'essa una sommatoria notevole


Ciao!
probid
Starting Member
Starting Member
 
Messaggio: 34 di 40
Iscritto il: 01/10/2010, 19:30

Re: Calcolo complessità algoritmo

Messaggioda Nepler265 » 07/12/2019, 16:20

sì, studio a Perugia ahaha :-D

grazie per i consigli comunque !
Nepler265
Starting Member
Starting Member
 
Messaggio: 15 di 25
Iscritto il: 18/09/2019, 11:05


Torna a Informatica

Chi c’è in linea

Visitano il forum: Nessuno e 18 ospiti