Oszacowanie złożoności asymptotycznej

Witam, czy ktoś potrafi wytłumaczyć jak obliczać złożoności asymptotyczną w takich zadaniach co podałem ale tak w prosty sposób bo to co znalazłem w sieci jest dla mnie nie czytelne, i nie potrafię tego zastosowań co moich zadań.

http://iv.pl/images/31265540461131420122.jpg

http://iv.pl/images/36285918018434604583.jpg

Pozdrawiam.

1. Wersja prosta: masz 3 pętle gdzie w każdej ogranicznikiem licznika jest n -> O(n³).
2. jw, znów 3 pętle gdzie ograniczeniem jest n -> O(n³). Ale jak chcesz wyliczyc to r to musisz jednak zrozumieć jak sumować ciągi arytmetyczne (bo rozumiem że to jest ta wersja która była dla ciebie "nie czytelna"?).
   Musisz to rozpisać jako ciąg arytmetyczny który mówi o tym ile razy wykonuje sie operacja w pętlach. Gdyby pętle były tylko te dwie pierwsze (i, j) to miałbyś obiegów:
   n,n-1,n-2,...,1
   Suma takiego ciągu n+n-1+n-2+...+1 = n*(n-1)/2
   A teraz musisz sobie analogicznie rozpisać coś takiego dla 3 pętli. Zauważ ze dla kazdego składnika podanego wyżej będziesz teraz miał znów ciąg wywołań. Na przykład dla członu n-2 z powyższego ciagu w przypadku 3 pętli masz zestaw wywołań: 1,2,3,4,...,n-2
   Więc cały ciag rozwiązań wygląda mniej więcej tak:
   (1,2,3,4,....,n) + (1,2,3,4,....,n-1) + (1,2,3,4,....,n-2) + ... + (1,2) + (1)
   No i teraz musisz to sumować jako ciągi arytmetyczne. Mamy więc:
   n*(n-1)/2 + (n-1)(n-2)/2 + (n-2)(n-3)/2 + ... + (2)(1)/2 + (1)(0)/2

Shalom napisał(a):

Suma takiego ciągu n+n-1+n-2+...+1 = n*(n-1)/2

Tutaj chyba powinno być n*(n+1)/2 ale mogę się mylić, a resztę muszę jeszcze prześledzić bo w tej chwili nie wiem o co chodzi. ; /
Bo dla n=3, pierwsza pętla wykona się i=3, druga j=6, trzecia k=20 czyli r=20.

http://pl.wikipedia.org/wiki/Ciąg_arytmetyczny#Suma_sko.C5.84czonego_ci.C4.85gu_arytmetycznego
jakieś +-1 mogą tam wyżej być źle, bo nie chciało mi sie rozkminiać szczególnie jak miałeś pętle od i=1 a nie i=0

Dla dwóch pętli działa, ale dla trzech coś nie działa, możesz jakoś jeszcze pomóc ?

U mnie działa