Kosz algorytmu i definicja klasy O(g) dla funkcji g

Odpowiedz Nowy wątek
2019-03-14 16:48
0

Cześć wszystkim. Mam na studiach przedmiot o nazwie algorytmy i struktury danych. Nasz wykładowca średnio mówi po polsku, dlatego czasem nie rozumiemy zbyt dobrze jego tłumaczeń niektórych zagadnień. Przekazał nam ostatnio próbny egzamin na którym m.in. widnieje zadanie o treści "Prosze zdefiniowac klase O(g) dla funkcji g : N ⇒ N". Nie bardzo wiem jak to działa, a na prawdziwy egzaminie może będzie podobne zadanie, więc jeśli ktoś umiałby to wytłumaczyć lub podesłać jakieś materiały to będę wdzięczna. :) Wykładowca czasem używa też określenia "koszt algorytmu", którego nigdy dokładnie nie wytłumaczył. Zrozumieliśmy tylko, że jakoś można to obliczyć, ale nie wiemy jak. :P Z góry dziękuję za pomoc i podpowiedzi.

Pozostało 580 znaków

2019-03-14 16:56

http://wazniak.mimuw.edu.pl/i[...]retna_1/Wykład_9:_Asymptotyka
Koszt algorytmu najczęściej jest rozumiany jako liczba operacji (jest to złożoność czasowa). Rozpatruje się też złożoność pamięciową (ile bajtów jest alokowane lub używane maksymalnie).

Pozostało 580 znaków

2019-03-14 17:00
1

Najpierw Rzuć okiem tutaj: Analiza Algorytmów , może Ci się rozjaśni - jeśli to o to chodzi. "Koszt algorytmu", o którym Piszesz, to może być koszt czasowy, tym zajmuje się analiza asymptotyczna, inaczej złożoność czasowa (algorytmy potrzebuja też pamięci - złozoność pamięciowa).
Jeśli ten krótki artykuł Ci nie wystarczy, to Weź swoją kopię CLRS, albo Udaj się do biblioteki i tam Znajdziesz wszystko.
Co do pytania, jaka to klasa funkcji w liczbach naturalnych? Obydwie funkcje: g(n) = n^2 oraz g(n) = n! są funkcjami N => N.


edytowany 1x, ostatnio: lion137, 2019-03-14 17:54

Pozostało 580 znaków

2019-03-15 08:52
0

Te klasy funkcji rozumiem tak: funkcja f jest klasy O(g) <=> istnieje takie k i M dodatnie, że dla każdego n>=k zachodzi f(n)/g(n) < M.
Czyli poczynając od pewnego k, f(n) i g(n) różnią się nie więcej niż M-krotnie.

edytowany 2x, ostatnio: yarel, 2019-03-15 08:52
Z tym że niestety masz problem jeśli g(n) <= 0. Gdybyś przerzucił to g na drugą stronę i dodał po obu wartość bezwzględną, byłoby spoko. - enedil 2019-03-16 02:03
@enedil: w ogólności masz rację. W tym przypadku autor pytania zaznaczył, że g działa z N do N. - yarel 2019-03-16 09:33

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