Złożoność pętli.

Witam mam oszacować następujące 2 złożoności:

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

oraz:

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

Używając notacji tetha:

koszt wykonania procedury P(i; j) wynosi tetha(1)
koszt wykonania procedury P(i; j) wynosi tetha (j).

Ok weźmy pierwszy przykład:

1: for i = 1 to n do <-- ta pętla wykona się tetha(n)
3: while j < n do <--- natomiast ta z racji przypisania wcześniejszego wykona się tetha(n-1)

Skoro poniższe instrukcje mają wartość tetha(1) to złożoność w 1 przypadku będzie równa tetha(n(n-1))= tetha(n^{2-n) = tetha(n}2)

Przykład nr 2 te same założenie:

Analogicznie jak w przypadku nr1 ponieważ i=j+j = tetha(1) bo jest pojedynczą instrukcją przypisania.

Przykład nr 1 na warunku 2:

Analogicznie z wyjątkiem takim , że while w środku będzie równy tetha(n) ponieważ j=n

Zatem tetha(n(n^{2-n) = tetha (n}3)

Przeykład nr 2 na warunku 2:

Analogicznie jak przykład nr1.

Proszę sprawdzić i ewentualnie poprawić. (zaznaczam,że to moje pierwsze przykłady z algorytmami.)

W drugim algorytmie będzie trochę inaczej. Zauważ, iż 'j' jest zwiększane 2 razy (a nie o ileś tam) więc rośnie kwadratowo, a nie liniowo (jak w pierwszym algorytmie). W złożoności powinien pojawić się pierwiastek.

Czyli wartość while w 2 przypadku będzie równa

n^2? czy jak bo juz sie pogubilem

Nie, nie n^2.

Startujemy licznik (j) od 1 i zwiększamy go dwukrotnie. I teraz pytanie - po ilu iteracjach licznik osiągnie n? Na pewno nie po n^2 iteracjach, odwrotnie ... ;)

czyli pierwiastek z n? to jakie by wyszly zlozonosci? 0o

Nawet nie pierwiastek, a co innego (pomyliłem się wcześniej :p ).

Pytamy, ile iteracji się wykona.
W kolejnych iteracjach j będzie wynosić kolejno 1, 2, 4, 8, 16, ... czyli j=2^x, gdzie x to numer iteracji. No i teraz pętla wykonuje się póki j<n czyli póki 2^x<n. Tak więc ile maksymalnie wyniesie x (ile iteracji zrobimy)?

2^n?

Ehhh, może tak:

No mi się wydaje, że 2^n bo jak podnosimy 2 do kolejno {0,1,2,3,4,5...n} to otrzymujemy ta iteracje {1,2,4,8,16...}

Kolego z tego równania masz:

x=log_{2}n

aynama napisał(a):

No mi się wydaje, że 2^n bo jak podnosimy 2 do kolejno {0,1,2,3,4,5...n} to otrzymujemy ta iteracje {1,2,4,8,16...}
Tu właśnie chodzi o dokładnie odwrotną sytuację.

{0,1,2,3,4,5**...} -> {1,2,4,8,16...n**}

tak zatem będzie to logn czyli z ewenętrznego while mamy nlogn ale jeszcze z zewnetrznej petli mamy n czyli zlozonosc bedzie rowna n(nlogn) = n^{2logn czyli zlozonosc bedzie rowna tetha (n}2)?

a w 2 przypadku by wychodzilo n^{3logn czyli tetha (n}3)?

Nie możesz tego logn wywalić. Jeśli coś wymaga log(n) operacji to złożoność nie wynosi Theta(1) tylko Theta(log(n)). Po prostu zostaw log(n) i będzie dobrze.

Czyli rozumiem , że w obu przypadkach mogę pozostawić wartości tetha(logn) tak? ok spoko ale pozostaje jeszcze ta pętla zewnetrzna o wartosci n czyli nasz ostateczny wynik nie bedzie czasem tetha(nlogn)?

Tak.

a ostatnie pytanie, czy dobrze oszacowałem jesli to P(i,j) ma koszt j no to jego wartosc to tetha(n)?