[Teoria złożoności] Ocena poprawności rozumowania

nowik1991 · Post autor: **nowik1991** » 11 lis 2012, o 20:43

1: for i = 1 to n do
2: j = i
3: while j < n do
4: sum = P(i; j)
5: j + +
6: end while
7: end for

Witam mam rozważyć na tym kodzie 2 przypadki:

1) Gdy \(\displaystyle{ P(i;j)}\) kosztuje nas \(\displaystyle{ 1}\)
2) Oraz gdy kosztuje nas \(\displaystyle{ j}\)

1) Bardzo łatwo można zauważyć, że będzie to złożenie \(\displaystyle{ \Theta (n \cdot n)=\Theta(n^2)}\)

2)Zauważmy, że nasza \(\displaystyle{ sum=j}\)

Zatem skoro zewnętrzna wykona się \(\displaystyle{ n}\) razy wewnętrzny while wykona się \(\displaystyle{ n^2}\) ponieważ będziemy mieć \(\displaystyle{ n}\) sum zatem złożoność tutaj będzie wynosić \(\displaystyle{ \Theta (n^2 \cdot n) = \Theta (n^3)}\)

Proszę ocenić tok mojego rozumowania.