[Teoria złożoności] Wylicz złożoność algorytmu

[pawlo392]

W jaki sposób oblicza się złożoność obliczeniową algorytmu?
Proszę o wytłumaczenie na prostym przykładzie, np :

Kod: Zaznacz cały

for i <--  -1 to 1
  do for j <--  -n to n 
   do if i*j>0
      then wypisz "coś"

[Pakro]

Moim zdaniem:
- pierwsza petla nie zależy od \(\displaystyle{ n}\) i powtarza sie \(\displaystyle{ 3}\) razy,
- druga jest zalezna od \(\displaystyle{ n}\) i jest wykonywa \(\displaystyle{ 2n+1}\) razy (mnożeń i porównań robi tyle samo).
Razem wychodzi \(\displaystyle{ 3(2n+1)}\) porównań (mnożeń) . Czyli wychodzi, ze złożoność to \(\displaystyle{ \theta(n)}\).