zagniezdzone petle a zlozonosc algorytmu

Odpowiedz Nowy wątek
2010-05-15 22:07

Rejestracja: 10 lat temu

Ostatnio: 1 rok temu

0

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>

  1. 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>

Pozostało 580 znaków

2010-05-15 22:27
Moderator

Rejestracja: 16 lat temu

Ostatnio: 18 minut temu

0

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)

Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...

Pozostało 580 znaków

2010-05-15 22:32

Rejestracja: 10 lat temu

Ostatnio: 1 rok temu

0

posta wyslalem wczesniej przez przypadek... :-/

Pozostało 580 znaków

abc
2010-05-15 22:32
abc

Rejestracja: 16 lat temu

Ostatnio: 11 godzin temu

Lokalizacja: Białystok

0
greep napisał(a)
  1. 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=(n2-3n+2)/2 => O(n2)

tak mi do glowy przyszlo

--- co do 4:

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

n*n/10=n2/10 => O(n2)


Pozostało 580 znaków

2010-05-15 23:10

Rejestracja: 10 lat temu

Ostatnio: 1 rok temu

0
abc napisał(a)

(n-2)* ((n-2)+1) /2=(n2-3n+2)/2 => O(n2)

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 n2, wtedy funkcja ma zlozoscia O(n2), 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>

Pozostało 580 znaków

2010-05-15 23:34
Moderator

Rejestracja: 16 lat temu

Ostatnio: 18 minut temu

0

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


Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...

Pozostało 580 znaków

2010-05-15 23:52

Rejestracja: 10 lat temu

Ostatnio: 1 rok temu

0

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... :-/ ?

</b>

Pozostało 580 znaków

2010-05-16 00:14
Moderator

Rejestracja: 16 lat temu

Ostatnio: 18 minut temu

0

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))


Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...

Pozostało 580 znaków

2010-05-16 00:18

Rejestracja: 10 lat temu

Ostatnio: 1 rok temu

0

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 ?

Pozostało 580 znaków

2010-05-16 15:27

Rejestracja: 15 lat temu

Ostatnio: 7 minut temu

0
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 ).


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.

Pozostało 580 znaków

2010-05-16 16:34

Rejestracja: 10 lat temu

Ostatnio: 1 rok temu

0
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:).

Pozostało 580 znaków

Odpowiedz

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0