Witam,
Mam pewien problem. Dostałem za zadanie zbadać wydajność algorytmów w programie napisanym w c#.
Wiem, że idzie zbadać wydajność czasową badając jak długo się algorytm wykonuje. Idzie zbadać złożoność obliczeniową ale to już na kartce policzyć wszelkie działania arytmetyczne.
Ale czy są jeszcze jakieś inne wydajności dla algorytmów? Bo ktoś mi wspomniał o wydajności pamięciowej tylko, że tutaj nie mam pojecia co i jak.
Proszę o jakąkolwiek pomoc.
Pozdrawiam.
Disclaimer: robię teraz za twojego belfra, mam nadzieje że mi odpali coś za to...
Zapoznaj się z terminem "złożoność obliczeniowa czasowa" i "złożoność pamięciowa".
Możesz do tego podejść teoretycznie (jak to opisałeś) lub empirycznie.
W tym drugim podejściu odpalasz program i mierzysz jego czas wykonania dla kontrolnej liczby elementów: 10, 100, 1000, 10000 itd.
Potem rysujesz wykres, gdzie X = liczba elementów, Y = czas wykonania i aproksymujesz do jakiej złożoności to pasuje.
Najprościej (metoda korporacyjna do liczenia w pamięci):
F(n) = czas wykonania dla n elementów
A = F(100)
B = F(1000)
C = B/A
D = 1000/100 = 10
E = C/D
Jeśli E > 1 to masz złożoność > niż liniowa.
Jeśli E > D to masz złożoność większą niż kwadratowa
Więcej o tym:
http://oxygene.ibspan.waw.pl/~sikorski/wi/wi_mpd06.pdf
OK,, dzięki za szybką odpowiedź .. czasowo obliczeniową już wiem jak obliczyć po poszperaniu w google ale nadal nie wiem co z pamięciową. Czy to się wgl liczy? .. Piszą, że to "określa z kolei liczbę komórek pamięci" jakie będą wykorzystywane podczas wykonywania algorytmu. No tak logiczne ale nigdzie nie piszą jak to badać..
Jeśli chodzi o złożoność pamięciową to ekspertem nie jestem, ale zakładam że chodzi o maksymalną liczbę jednostek pamięci (komórek, elementów struktury) które musisz alokować dla problemów N elementowych.
Przy czym przez komórkę niekoniecznie tu się rozumie bajt, może być integer, float, double itd.
Np. jeśli możesz przetworzyć zbiór algorytmem który zawsze alokuje tyle samo bajtów (np. pracuje na buforze) to masz złożoność O(1).
Więcej:
http://edu.i-lo.tarnow.pl/inf/utils/010_2010/0216.php