Złożoność obliczeniowa

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ć?

1

Treść zadania zobowiązuje Cie, do uwzględnienia wszystkich operacji jednostkowych - jakie to są ? - Nie wiem, w każdym 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.

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

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.

1

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

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