[Algorytmy] Boki trójkąta - złożoność obliczeniowa czasowa

[Cryer]

Witam,
mam problem z okresleniem zlozonosci czasowej algorytmu sprawdzajacego czy z kazdych n patykow da sie zbudowac trojkat, tzn. mamy n liczb (n>=3) i sprawdzamy czy z kazdej trojki liczb mozna zbudowac trojkat.

Algorytm wyglada tak:

Kod: Zaznacz cały

 for(k=0; k+2<n; k++)              
        for(j=k+1; j+1<n; j++)        
            for(i=j+1; i<n; i++) {    
                if(tab[k]<(tab[j]+tab[i]) && tab[i]<(tab[j]+tab[k]) && tab[j]<(tab[i]+tab[k])) 
              cout<<"Z patykow: "<<tab[k]<<" "<<tab[j]<<" "<<tab[i]<<" mozna stworzyc trojkat"
                else 
              cout<<"Z patykow: "<<tab[k]<<" "<<tab[j]<<" "<<tab[i]<<" nie mozna stworzyc trojkata"
             }

Nie jestem pewien czy jest to zlozonosc rzedu O(n^3), czy moze jakas wykladnicza?
Alorytm wykonuje tyle operacji ile jest 3-elementowych podzbiorow(kombinacji) w zbiorze n-elementowym.

Czy ktos moglbym jednoznacznie okreslic jaka to klasa zlozonosci? A moze ktos jest w stanie okreslic dokladna zlozonosc?

Prosze o pomoc
Pozdrawiam
Cryer

[Afish]

Sprawdzasz każdą trójkę, trójek jest \(\displaystyle{ {n \choose 3} = \frac{n\left(n-1\right)\left(n-2\right)}{6}}\) a to jest asymptotyczne \(\displaystyle{ O(n^3)}\)

[Cryer]

Swietnie, cos podobnego kombinowalem ale nie bylem pewien.
Bardzo dziekuje za pomoc