Złożoność obliczeniowa

Odpowiedz Nowy wątek
2015-09-02 10:45
1

Witajcie, mam ostatnio problem z całą złożonością obliczeniową algorytmów na przedmiocie Algorytmy i struktury danych. Czy jest osoba, która może podrzucić odpowiednie materiały do nauki złożoności? Nie ukrywam, że mam problem, jeżeli chodzi o rozwiązanie najprostszego zadania. Nie rozumiem, dlaczego w tym zadaniu pojawił się tak, a nie inny wynik.

http://imgur.com/tvzEr8g

Ktoś mógłby pomóc i wytłumaczyć?

Pozostało 580 znaków

2015-09-02 11:00
1

Treść zadania zobowiązuje Cie, do uwzględnienia wszystkich operacji jednostkowych - jakie to są ? - Nie wiem, w każdym bądź razie zakreśliłeś ołówkiem.
2 - to są początkowe dwa pierwsze przypisania.
5y - no bo razem z porównaniem w pętli masz 5 operacji jednostkowych, zaś pętla się wykona y razy
+1 - ostatnie porównanie w warunku pętli (gdy i = y) (nie wejdziesz już do środka)
razem 5y+3 = O(y) - to z definicji notacji O.

Pozostało 580 znaków

2015-09-02 11:05
1

Ale co tam tłumaczyć? Masz policzyć ile jednostkowych operacji wykona algorytm. Operacje to zwykle: operacje matematyczne, porównania, przypisania.
Patrzysz na swój algorytm i widzisz że w każdym obiegu pętli wykonujesz:

  • jedno porównanie i<y
  • jedno mnożenie z*x
  • jedno dodawanie i+1
  • dwa przypisania i=i+1 oraz z=z*x
    W sumie 5 operacji.
    Pętla wykonuje się y razy więc masz w pętli 5y operacji. Dodatkowo masz tam jeszcze pewne stałe operacje inicjalizacji algorytmu (np. te dwa przypisania na początku) ale w praktyce one nigdy nie mają znaczenia bo niezależnie od danych mają koszt stały O(1). Interesuje cię tylko część algorytmu zależna od rozmiaru danych wejściowych. Widać tutaj że mamy takich operacji 5y czyli rząd złożoności jest liniowy -> O(y). To oznacza że jeśli zwiększysz y 10 razy to algorytm będzie działał 10 razy wolniej.

Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...
@Shalom, algorytm będzie działał 10 razy dłużej, ale nie będzie działał ani trochę wolniej.:P - bogdans 2015-09-02 13:32

Pozostało 580 znaków

2015-09-02 13:30
0

Dziękuję bardzo Wam za odpowiedź. Rozjaśniliście mi trochę, na czym polega złożoność obliczeniowa algorytmów. Nadal tylko nie wiem, dlaczego złożoność jest rzędu liniowego, ale to już chyba braki w wiedzy teoretycznej :f

Pozostało 580 znaków

2015-09-02 14:11
0

Dlaczego O(n) jest złożonością liniową, O(n^2) - kwadratową, O(1) - stałą. Faktycznie, to wina poważnych braków teoretycznych.


"A human being should be able to change a diaper, plan an invasion, butcher a hog, conn a ship, design a building, write a sonnet, balance accounts, build a wall, set a bone, comfort the dying, take orders, give orders, cooperate, act alone, solve equations, analyze a new problem, pitch manure, program a computer, cook a tasty meal, fight efficiently, die gallantly. Specialization is for insects." Robert Heinlein.

Pozostało 580 znaków

2015-09-02 14:16

Och bo notacja O usuwa wszystkie wyrazy niższego rzędu zostawiając tylko ten wiodący. Masz np. tutaj 5y+3. Jeśli za y podstawisz na przykład miliard to to +3 w zasadzie nie ma już znaczenia. Im większe dasz y tym mniejsze znaczenie ma ten wyraz niższego rzędu. Stałą 5 też można wyrzucić z podobnych powodów, bo jak cos się ma wykonywać miliard razy dłużej czy pięć miliardów to już nie jest taka wielka różnica.
Analognicznie jeśli masz na przykład n^2^+n to będzie O(n2) bo zauważ że n2 rośnie dużo szybciej niż n więc dla odpowiednio dużego n ten wyraz wolny będzie pomijalnie mały. Np. dla 1000 będziesz miał 1000000+1000. Czy robi ci różnicę czy algorytm wykonuje się 1000000 razy dłużej czy 1001000 razy dłużej? ;)


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

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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