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.
0
1
http://wazniak.mimuw.edu.pl/index.php?title=Matematyka_dyskretna_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).
1
Najpierw Rzuć okiem tutaj: https://4programmers.net/Algorytmy/Analiza_asymptotyczna , 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.
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.