zagniezdzone petle a zlozonosc algorytmu

Jesli ktos rozwiazylal juz takie zadania, pewnie nie bedzie mial problemu :)

Chodzi o obliczenie zlozonosci algorytmu (Notacja Wielkie O) dla paru funkcji.

Np:

1. Jesli mamy mamy 1 petle FOR:

for (i= 1 ; i <n ; i++)
{ statement };

To zlozonosc tego algorytmu bedzie liniowa, O(n)

2. Jesli mamy 2 petle FOR (jedna zagniezdzona w drugiej):

for (i= 1 ; i <n ; i++)
{
for (j=1; i<n ; j++ )
{ statement };
}

To zlozonosc tego algorytmu bedzie do n do kwadratu, O(n^2), bo za kazdym 'i', wywolujemy 'j' n razy, czyli np: dla n=4, bedziemy mieli
i=1, j=1
i=1, j=2
i=1, j=3
i=2, j=1
i=2, j=2
i=2, j=3
i=3, j=1
i=3, j=2
i=3, j=3

Czyli n*n porownan = n^2 porownan.</span>

3. Jaka bedzie zlozonosc algorytmu np: tego:

for (i = 1 ; i < n ; i ++)
{
for (j= i+1 ; j < n ; j++)
{
Statement
}
}

Np: dla n=3,
i=1, j=2
i=1, j=3
i=2, j .... juz sie nie wykonuje
Za pierwszym razem (dla i=1 nie wykonal sie liniowo, bo wykonal j=2 i j=3 ale przeskoczyl j=1).
Czyli wydaje sie ze jest to cos wiecej niz liniowy.
Dla i=2 natomiast nie wszedl w ogole druga petle tak wiec tutaj wykonal sie liniowo.

Jak go ogolnie zaklasyfikowac?

4. I ostatni algorytm:

int product = 1;
for ( int i = 10; i <= n; i += 10 ) {
for (int j = n; j > 0; j -- ) {
product *= ( i * j );
}
}</span>

</b></b>

Najpierw pisze się posta, a potem go wysyła, nie chce mi się czekać na kolejne "dopiski"

1. tak
2. tak
3. O(n^2) bo masz tutaj sumę szeregu:
   [suma od i=1 do i=n] (n-i) = (n-1) + (n-2) + ... + 1 = (n-1)*(n-1+1)/2 = O(n^2)

posta wyslalem wczesniej przez przypadek... :-/

greep napisał(a)

3. Jaka bedzie zlozonosc algorytmu np: tego:

for (i = 1 ; i < n ; i ++)
{
for (j= i+1 ; j < n ; j++)
{
Statement
}
}

i wywolujemy n-1 razy
a j zawsze co kazde takie wywolanie o 1 raz mniej (zaczynamy od n-2), liczac same j:

(n-2)+(n-3)+(n-4)+...3+2+1=[Suma ciagu aryt.] (n-2)*((n-2)+1)/2=(n^{2-3n+2)/2 => O(n}2)

tak mi do glowy przyszlo

--- co do 4:

i -> podloga(n/10)
j -> n

n*n/10=n^{2/10 => O(n}2)

abc napisał(a)

(n-2)* ((n-2)+1) /2=(n^{2-3n+2)/2 => O(n}2)

Dopiero teraz przeczytalem cos o ciagach.
Czyli to co napisales powyzej, to jest : "srednia pierwszego i ostatniego wyrazu ciagu"?

Pierwszy wyraz to: (n-2)
Ostatni wyraz to: ((n-2)+1) ten '+1' to dlatego ze w funkcji przy 'j' jest 1'j=i+1'?

Dlaczego ignorujemy zewnetrzna petle w obliczeniach (czy mi sie zdaje)?

Jesli wynik mnozenia pierwszej i ostatniej liczby w ciagu daje n^{2, wtedy funkcja ma zlozoscia O(n}2), tak?
Gdybysmy z mnozenia pierwszej i ostatniej liczy w ciagu nie otrzymali n^2, tylko n jako najwieksza wartosc, wtedy zlozonosc tej funkcji bylaby liniowa O(n)? tak?

Czy moglbys w jakis latwy sposob zmodyfikowac powyzsza funkcje '3' tak zeby jej zlozonosc stala sie liniowa i jeszcze raz napisal obliczenie (pomoze mi to nauczyc sie odrozniac poszczegolne zlozonosci).

pozdrawiam i z gory dziekuje</quote>

Doczytaj chłopie coś o ciągach i szeregach ;]
Bo to co piszesz to jakiś bełkot.

pierwszy wyraz = 1
ostatni wyraz = n-2
ilość wyrazów = n-2
Suma takiego ciągu to jest: ilość wyrazów * (ostatni wyraz + pierwszy wyraz)/2 = (n-2) * (n-2 + 1)/2

Niczego nikt nie zignorował. Złożoność masz O(n^2) jak pojawi ci się gdzieś wyraz w drugiej potędze.
Na chłopski rozum: jeśli masz jedną pętlę to z reguły masz liniową złożoność, jak masz dwie pętle to kwadratową etc. Nie jest to regułą, ale w 90% tak ;]

btw: takich podstaw na temat ciągów i szeregów uczą przecież w liceum (i to w 2 klasie chyba), jak to jest możliwe że ty jesteś studentem i tego nie umiesz? o_O

No zapomnialem co nieco przez pare lat :D
Teraz juz jest duzo jasniej :)
Tylko 1 pytanie:

Gdybysmy mieli trzy zagniezdzone petle np:

for (i= 1 ; i <n ; i++)

  for (j=1; j<n ; j++ )

          for (k=1; k<n ; k++ )      

                 { statement }

pierwszym wyrazem ciagu jest: 1
ostatnim: n-1
ilosc wyrazow: n-1

podstawiajac pod wzor: (n-1) * ((n-1)+1) / 2
nie wychodzi z tego n^3 a chyba powinno?
czy znowu gdzies robie blad... :-/ ?

Tak się mozesz bawić jak liczniki pętli są skorelowane, tak jak powyzej. Tutaj nie musisz tak cudować. Na chłopski rozum widać ze:
dla każdego obrotu pętli zewnętrznej (po i) pętla środkowa (po j) wykona się n-1 razy, a dla każdego obrotu pętli środkowej pętla wewnętrzna (po k) wykona się n-1 razy.
O((n-1)(n-1)(n-1)) = O(n^3)

A jeśli musisz z ciągami to zauważ że policzyłeś to tylko dla jednej pętli!
W tym wypadku ciąg dla pętli wewnętrznej składa się z trójki (i,j,k) a nie tylko z jednej liczby!

Inaczej możesz to sobie rozpisać jako sumę:
[Suma od i=1 do n]([Suma od j=1 do n](Suma od k=1 do n))

Dzieki za odpowiedzi

Algortymy z 2 zagniezdzonymi petlami wydaja sie byc mnie jasne, ale z 3 zagniezdzonymi petlami jednak dalej nie... :-/

Wiem, ze ta powyzsza funkcja (3 zagniezdzone petle) jest najprostsza z mozliwych i golym okiem widac, ze jej zlozonosc to O(n^3), jednak dalej nie wiem dokladnie jak mialbym to rozpisac przy uzyciu ciagow...
Dales mi co prawda wskazowki, zeby rozpisac trzeba rozpisac na 3 petle albo rozpisac sume... ale nigdy wczesniej nie widzialem takiego 'ukonczonego' przykladu.
A bez przykladu to niestety moge tylko gdybac jak to powinno wygladac.
Gdy bede mial wzor, mysle ze uda mi sie rozwiazac trudniejsze przyklady z 3 zagniezdzonymi petlami.

Jesli masz, chwilke bede wdzieczny gdybys napisal jak doszedles do rozwiazania O(n^3) dla powyzszej petli uzywajac ciagow i rozpisujac sume.
Czy uzywajac ciagow, rozpisujemy 3 osobne petle (podobnie jak ja powyzej zrobilem dla jednej)?
Jesli tka, to jak je potem laczymy, zeby uzyskac wynik z n^3 ?

greep napisał(a)

Gdybysmy mieli trzy zagniezdzone petle np:

for (i= 1 ; i <n ; i++)

  for (j=1; j<n ; j++ )

          for (k=1; k<n ; k++ )      

                 { statement }

pierwszym wyrazem ciagu jest: 1
ostatnim: n-1
ilosc wyrazow: n-1

podstawiajac pod wzor: (n-1) * ((n-1)+1) / 2
nie wychodzi z tego n^3 a chyba powinno?
czy znowu gdzies robie blad... :-/ ?
</b>

Wychodzi dokładnie (n - 1) ^{3 czyli O(n} 3) (ale nie z tego wzoru co podałeś). Nie wiem gdzie widać problem.

Poza tym bardzo często n zagnieżdżonych pętli ma złożoność mocno asymptotycznie mniejszą. Np KMP ma pętlę zagnieżdżoną w obu pętlach licznik może przyjmować wartości od 1 do n, a mimo to cały algorytm jest liniowy, a nie kwadratowy. Cały myk tutaj jest w tym że indeksy nie lecą po kolei ale mogą przeskakiwać o jakąś tam liczbę pozycji. Do liczenia złożoności stosuje się szereg różnych technik (np indukcja matematyczna) i jest to temat na cały przedmiot na studiach (u mnie jest taki przedmiot i to jest hardkor ;]). Spróbuj policzyć na kalkulatorze np złożoność zamortyzowaną i pesymistyczną drzew rozchylanych ( http://en.wikipedia.org/wiki/Splay_tree ) czy kopców Fibonacciego ( http://en.wikipedia.org/wiki/Fibonacci_heap ).

donkey7 napisał(a)

Wychodzi dokładnie (n - 1) ^{3 czyli O(n} 3) (ale nie z tego wzoru co podałeś). Nie wiem gdzie widać problem.

a moglys to obliczyc ze wzoru na ciag arytmetyczny (dla tych 3 zagniezdzonych petli).
Chcialbym zobaczyc w jakis sposob uzyskujesz n^3 (z uzyciem wzoru na ciagi:).

WTF??? Co to za wzór na ciągi??? Chyba wystarczy jak policzysz ilość kroków co do oczka? Co ten ciąg ma zawierać?

Jemu chyba chodzi o zapis
)%20=%20%5Csum_{i=1}^{n-1}(%5Csum_{j=1}^{n-1}(1%20%5Ccdot%20(n-1))%20=%20%5Csum_{i=1}^{n-1}(1%20%5Ccdot%20(n-1)%20%5Ccdot%20(n-1))%20=%20(n-1)%20%5Ccdot%20(n-1)%20%5Ccdot%20(n-1)%20=%20O(n^3))
;]
Tutaj nie trzeba nigdzie stosować wzoru na sumę ciągu arytmetycznego...

edit: dzieki, poprawione ;)

Mały błąd masz - ograniczenie górne to n - 1 a nie n.

Ok, jesli powyzej nie trzeba stosowac tego wzoru, to moze w ponizszym przykladzie trzeba :) Ten jest troche trudniejszy...
Bo chyba wlasnie stostowanie tego wzoru doprowadza nas do obliczenia zlozonosci funkcji? Czy znowu sie myle...?

Nie wiem jak dojsc do rozwiazania, wiem ze zlozonosc ma wyjsc O(n^2).

Czy mozna tez dojsc do rozwiazania po prostu podstawiajac liczby?
Jesli tak, to w jaki sposob?
Dla n=3, petla:
i wykonuje sie 3 razy
petla:
j wykonuje sie 1 raz
petla:
k wykonuje sie 3 razy
Czy zeby funkcja miala zlozonosc O(n^3), kazda petla musialaby byc wykonywana 3 razy?
Jesli jedna z petli wykonywalabylaby 2 razy, a pozostale 3 razy, to zlozonosc tego algorytmu jest automatycznie O(n^2)?
Jak (modyfikujac ilosc wykonywanych petli) mozna zmniejszyc zlozonsc ponizszego algorytmu do liniowej O(n)?

W tym wypadku warunek j % i == 0 działa tak samo jak j == i bo j <= i. Tutaj trzeba zliczyć ilość ciągów typu (i, j, k) gdzie k < j <= i, a takowych jest O(n ^{3). Shalom umie pisać wzorki to zaraz pewnie napisze ;p Zakładając że obsługa jednej iteracji pętli zajmuje 0 czasu to zejdziemy do O(n} 2) tzn tyle będzie mnożeń w samym środku.

donkey7 napisał(a)

W tym wypadku warunek j % i == 0 działa tak samo jak j == i bo j <= i. Tutaj trzeba zliczyć ilość ciągów typu (i, j, k) gdzie k < j <= i, a takowych jest O(n ^{3). Shalom umie pisać wzorki to zaraz pewnie napisze ;p Zakładając że obsługa jednej iteracji pętli zajmuje 0 czasu to zejdziemy do O(n} 2) tzn tyle będzie mnożeń w samym środku.

No wlasnie o taki wzorki mi chodzilo :)
Jesli bede miec dobry przyklad obrazujacy jak dojsc do rozwiazania tego konkretnego przykladu, to moze w koncu to zrozumiem :D

greep napisał(a)

Nie wiem jak dojsc do rozwiazania, wiem ze zlozonosc ma wyjsc O(n^2).

int product = 1; for ( int i = 1; i <= n; i ++ ) { for ( int j = 1; j <= i; j ++ ) { if ( j % i == 0 ) { for ( int k = 0; k < j; k ++ ) { product *= (i * j); } } } }

Ok, na razie nikt nie zaproponowal wzoru na obliczenie tego, wiec pytam, czy ponizszy sposob dojscia do rozwiazania jest poprawny dla powyzszej petli? :

1. Przypuscmy ze n=4. Sprawdzam ilosc wykonan ostatniej petli 'k' dla poszczegolnych wartosci 'n'

Czyli:
dla n=1, petle k wykonujemy 1 raz
dla n=2, petle k wykonujemy 2 razy
dla n=3, petle k wykonujemy 3 razy
dla n=4, petle k wykonujemy 4 razy

co daje nam ciag: 1+2+3+4+...+n (n bo za kazdym zwiekszeniem 'n' o jeden, petle 'k' wykonujemy 'n' razy).

Teraz, korzystajac z wzoru na sume ciagu arytmetycznego:
n = dlugosc ciagu
1 = pierwszy element ciagu
n = ostatni element ciagu

n(n+1)/2 = (n^2+n)/2 w uproszeniu dla notacji Wielkie O, zlozonosc wynosci O(n</sup>2).

Rozwiazanie moze troche czasochlonne bo musimy przesledzic algorytm i wypisac poszczegolne liczby, ale... jesli jest poprawne great :)

Wracajac do petli, gdzie zlozonosc O(n^3) jest oczywista:

for (i= 1 ; i <n ; i++)
for (j=1; j<n ; j++ )
for (k=1; k<n ; k++ )
{ statement }

Postepujac w ten sam sposob jak powyzej, czyli sprawdzamy ilosc wykonan ostatniej petli 'k' dla poszczegolnych wartosci 'n'

Czyli:
dla n=1, petle k wykonujemy 1 raz
dla n=2, petle k wykonujemy 4 razy
dla n=3, petle k wykonujemy 9 razy
dla n=4, petle k wykonujemy 16 razy

co daje nam ciag: 1+4+9+16+...+n² (n</sup>2 bo za kazdym zwiekszeniem 'n' o jeden, petle 'k' wykonujemy 'n^2' razy).

Teraz, korzystajac z wzoru na sume ciagu arytmetycznego:
n = dlugosc ciagu
1 = pierwszy element ciagu
n^2 = ostatni element ciagu

n ((n^{2) +1) / 2 = (n}3+ n) / 2 w uproszeniu dla notacji Wielkie O, zlozonosc wynosci O(n^3).

Jak na razie powyzsza metoda, to jedyna ktora ma dla mnie sens przy rozwiazywaniu tego typu zadan, ale... CZY JEST POPRAWNA????</span>

Istnieje też jeszcze jedna metoda - ograniczenie z góry i z dołu.
Jeżeli uda się nam ograniczyć daną funkcję zarówno z góry, jak i z dołu tą samą funkcją, to badana funkcja będzie asymptotycznie równa funkcji ograniczającej.

np.

for(int i=0;i<n;i++)
   for(int j=i;j<n;j++)
      //cokolwiek

Ograniczenie z góry:
Przyjemy, że j == n w wewnętrznej pętli i mamy O(n^2) obrotów pętli.

Ograniczenie z dołu:
Odrzucamy pierwsze n/2 obrotów zewnętrznej pętli (j jest więc zawsze >= n/2).
Przyjmujemy, że j==n/2 (jeszcze bardziej ograniczamy z dołu) i otrzymujemy O(n/2 * n/2) = O(n^2) obrotów.

W sumie mamy więc O(n^2).

Ograniczenie z dołu oznaczamy inaczej niż "O", ale niestety nie pamiętam jak.

dzieki za odp.
nie potwiedziles tylko czy moja metoda jest poprawna?
domyslam sie, ze tak bo jej nie zaprzeczyles ale... fajnie byloby uslyszec potwierdzenie :)

A odnosnie tych innych notacji to chyba miales na mysli Theta i Omega?

Twoja metoda jest błędna. Czemu? Bo nadal nie raczyłeś powtórzyć sobie sumowania szeregów.
To co masz
1 + 4 + 9 +... + n^2 nie jest ciągiem arytmetycznym, więc nie wolno ci użyć wzoru o którym pisałem wcześniej, bo on tutaj nie pasuje.

Masz policzyć sumę szeregu
<image>
http://latex.codecogs.com/gif.latex?%5Csum_{k=1}^{n}(k^2)
</image>

Nie chce mi sie teraz myśleć jak tą sumę liczyć, pewnie całkując / różniczkując szereg itd,
wolframaplha mówi ze wynik to

Ok,

W sumie znalazlem w internecie jakies wzory, ale nie wiem jak ich uzyc...
Na ich podstawie (trzeci wiersz tabeli od gory) podstanowilem podstawic wzor na sume ciagu aryt... :-/

http://math2.org/math/expansion/power.htm

Czy przez te wzory mam rozumiec, ze w zaleznosci od dlugosci ciagu (ilosci petli), musimy uzywac innego wzoru?

• gdybym mial czas, to pewnie bym sobie wszystko ladnie powtorzyl i wyszukal, ale nie mam... :-/

A z drugiej strony, to nawet patrzac na te liczby (ilosc wywolan ostaniej petli 'k') nie mozna jedno znacznie stwierdzic zloznosci?

Np: jesli:

n=1 k=1
n=2 k= 1
n=3 k=1
To mamy zloznosc liniowa O(n)

Jesli:
n=1 k=1
n=2 k=2
n=3 k=3
To mamy zlozonosc O(n^2)

Jesli:
n=1 k=1
n=2 k=6 (czyli (n^2)+2 )
n=3 k=11
n=4 k=18
To mamy zlozonosc O(n^3)

Czy takie cos nie bedzie wiarygodne/prawdziwe?

Nie. W zależności od tego jaki ciąg sumujesz.
Tutaj miałeś ciąg 1 + 4 + .. + n^2, który nijak arytmetyczny nie jest...

Shalom napisał(a)

Nie. W zależności od tego jaki ciąg sumujesz.
Tutaj miałeś ciąg 1 + 4 + .. + n^2, który nijak arytmetyczny nie jest...

Czyli wszystko zbiega do tego jaka jest roznica (czym mozna ja wyrazic) pomiedzy kolejnymi wyrazami ciagu, tak?