Pagina 1 di 1

Calcolo complessità algoritmo

MessaggioInviato: 07/12/2019, 13:18
da Nepler265
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 ?

Re: Calcolo complessità algoritmo

MessaggioInviato: 07/12/2019, 15:36
da probid
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!

Re: Calcolo complessità algoritmo

MessaggioInviato: 07/12/2019, 16:20
da Nepler265
sì, studio a Perugia ahaha :-D

grazie per i consigli comunque !