• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Problem z Big-O

VPS Starter Arubacloud
0 głosów
283 wizyt
pytanie zadane 18 lutego 2018 w Matematyka, fizyka, logika przez jegor377 Stary wyjadacz (13,230 p.)
edycja 18 lutego 2018 przez jegor377

Dzień dobry! Czytam pewną książkę na temat algorytmów i tym podobnych, i jestem na rozdziale związanym z Big-O/Time Complexity. Mój problem polega na tym, że nie do końca rozumiem przykład zastosowany w książce (daje screena), ponieważ przejrzałem też parę filmów na yt (a dokładniej chodzi mi o ten: https://youtu.be/v4cd1O4zkGw?t=2m50s) i to co jest w książce nie do końca się zgadza z tym co jest w internecie (tzn. pewnie się zgadza, tylko ja tego nie widzę).

W książce napisane jest, że pętle zagnieżdżone dla jednego zbioru (listy/tablicy) należy do siebie dodawać (a przynajmniej te w przykładzie), a na filmie jest powiedziane, że należy je mnożyć przez siebie, jeżeli odnoszą się do tej samej listy.

Spróbowałem zrobić przykład z książki za pomocą mnożenia, ale wychodzą mi jakieś dziwne rzeczy.

Proszę, czy mógłby mi to trochę bardziej objaśnić i pokazać co robię źle? Poniżej zamieszczam screena z książki.

 

1 odpowiedź

+1 głos
odpowiedź 18 lutego 2018 przez Aisekai Nałogowiec (42,190 p.)

Mnoży się. Jeżeli masz dwie zagnieżdżone pętle np:

for(int i=0; i<n; i++){
     for(int j=0; j<m; j++){
//jakiś kod
            }
}

to pętla wewnętrzna wykona się (o ile "jakiś kod" jej nie przerwie) m*n (m iteracji wewnętrznej pętli i n iteracji zewnętrznej pętli). W książce też jest dobrze napisane. Zauważ, że on dodaje do siebie ile iteracji wewnętrznej pętli będzie, z każdą kolejną iteracją zewnętrznej pętli.

W pierwszej iteracji zewnętrznej będzie n-1, w drugiej n-2, w trzeciej n-3 itd. aż będzie 1. Sumując to ze wzoru na sumę ciągu arytmetycznego dostajesz odpowiedź, że ilość iteracji będzie wynosić (n^2-n)/2. Najszybciej rośnie n^2 więc złożoność będzie wynosić O(n^2) (kwadratowa)

komentarz 19 lutego 2018 przez jegor377 Stary wyjadacz (13,230 p.)

No dobrze, tą część z sumowaniem tych pętli zewnętrznych rozumiem, ale zobacz na ostatni akapit.

Ja rozumiem ten tekst jako: "W najgorszym przypadku, warunek jeżeli jest zawsze spełniony. To oznacza, że pętla wewnętrzna wykonuje jedno porównanie i jedno przypisanie (n^2 - n)/2 razy, stąd n^2 - n operacji" - Tutaj rozumiem, że to jest n^2 - n, ponieważ pętla wewnętrzna wykonuje 2 instrukcje w każdej iteracji i należy ilość instrukcji (2) pomnożyć przez ilość iteracji ( (n^2 - n)/2 ) i wtedy wychodzi, że każda pętla wewnętrzna wykonuje n^2 - n operacji. Tutaj jeszcze rozumiem.

Potem jest "Ostatecznie, algorytm kosztuje 2n - 2 operacji dla pętli zewnętrznej (Tutaj również rozumiem. Pętla zewnętrzna wykonuje dwie operacje - przypisanie currenta i swapa.), plus n^2 - n operacji dla pętli wewnętrznej" - i po tym przecinku z plusem przestaje rozumieć.

Skoro pętla zewnętrzna wykonuje 2n - 2 operacji, a wewnętrzna n^2 - n, to dlaczego nie można ilości operacji tych dwóch pętli pomnożyć przez siebie, tylko należy je do siebie dodać?

Reszta jest zrozumiała. Tylko ten jeden element mi umyka. Jeżeli w twojej odpowiedzi jednak jest zawarta pełna odpowiedź na moje pytanie, a ja jestem głupi albo ślepy i nie widzę, to przepraszam i dziękuję za cierpliwość. Chcę to zrozumieć, ale idzie mi to bardzo ciężko. :|

komentarz 19 lutego 2018 przez Aisekai Nałogowiec (42,190 p.)
Czemu należy dodać? Bo liczysz liczbę wszystkich operacji. Skoro w zewnętrznej pętli masz dwie operacje i wykonuje się n-1 razy to w pętli zewnętrznej masz 2n-2 operacji. W pętli wewnętrznej (w najgorszym przypadku, kiedy if zostanie spełniony) masz też 2 operacje, ale pętla wykona się (n^2-n)/2 razy więc łącznie z wewnętrznej pętli będziesz miał n^2-n operacji. Dodając do siebie:

n^2-n i 2n-2 wychodzi, że masz n^2+n-2 operacje w całym algorytmie.
komentarz 19 lutego 2018 przez jegor377 Stary wyjadacz (13,230 p.)
Dobrze, już rozumiem chyba. Czyli dodaje, bo to jest po prostu liczba operacji jakie tam nizej zostana wykonane dla kazdego n. Mam jeszcze taka mysl, ktorej nie jestem pewiem i wole zapytac, a brzmi ona tak: liczba operacji z petli wewnetrznej jest niezalezna od liczba operacji petli zewnetrznej. Mysle, ze po twojej nastepnej odpowiedzi juz nie bede mial niedopowiedzen. Przepraszam, ze jestem taki oporny i dziekuje jeszcze raz za cierpliwosc. :)
komentarz 19 lutego 2018 przez Aisekai Nałogowiec (42,190 p.)
Nie wiem co u Ciebie oznacza "niezależna".

Z przykładu: w pętli wewnętrznej masz dwie operacje (przypisanie i porównanie) w pętli wewnętrznej która wykona się n-1 razy, czyli w pierwszej iteracji zewnętrznej pętli zostanie wykonanych 2n-2 operacje wewnętrznej pętli. W następnej masz 2n-4 itd, aż pętla wewnętrzna wykona się raz, czyli będziesz miał dwie operacje. I teraz trzeba zsumować liczbę operacji z każdą iteracja zewnętrznej pętli (2n-2+2n-4+2n-8+...+2).

Natomiast w zewnętrznej pętli, masz 2n-2 operacje.

Podobne pytania

0 głosów
1 odpowiedź 156 wizyt
pytanie zadane 31 sierpnia 2019 w Matematyka, fizyka, logika przez amelia.cpp Obywatel (1,860 p.)
0 głosów
1 odpowiedź 262 wizyt
0 głosów
0 odpowiedzi 394 wizyt

92,455 zapytań

141,263 odpowiedzi

319,099 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...