złożoność czasowa i pamięciowa

Odpowiedz Nowy wątek
2011-03-25 20:48
0

Czy istnieją w c++ gotowe funkcje obliczające złożoność czasową i pamięciową innej funkcji ? nie muszą być dokładne, chodzi mi jedynie o przedstawienie w programie, że algorytm c jest wydajniejszy od b

Jeżeli nie ma żadnych gotowców to proszę o wskazówki jak mam w ogóle zabrać się do tego.

Pozostało 580 znaków

2011-03-25 20:54
0

Krótka odpowiedź - nie. Dłuższa odpowiedź - nie wiem nawet jak procedura wyznaczania takiej złożoności ma wyglądać, pewnie zrobienie ogólnej funkcji nie będzie nawet możliwe. Najprostszym rozwiązaniem jest chyba przygotowanie alternatywnych algorytmów i przetestowaniu ich dla pewnych, zgodnych ze spodziewanym danymi, testów.

Dodatkowo, jaki algorytm jest lepszy, quicksort czy mergesort. Obydwa mają identyczną spodziewaną złożoność, ale dla mergesort nawet dla niekorzystnych danych nlogn jest zachowane, w quicksorcie nie. Ale quicksort jest zwykle o wiele szybszy (choć nie wiem czy takie taśmowe algorytmy nie wrócą do łask przy dalszym rozwarstwianiu się szybkości pamięci i procesora).

edytowany 1x, ostatnio: Zjarek, 2011-03-25 20:58

Pozostało 580 znaków

2011-03-25 20:58
0

Nie istnieją takie funkcje w żadnym języku programowania (elementarne), a badanie złożoności obliczeniowej jest osobną dziedziną nauki. Do badania tejże złożoności wykorzystuje się abstrakcyjne modele np. maszyne Turinga. Polecam Wikipedie.


:)

Pozostało 580 znaków

2011-03-25 21:03
0

Coś mi świta w głowie, że bodajże w pascalu była instrukcja licząca czas działania get time ma to może swój odpowiednik w c++ ?
W sumie źle się wyraziłem, nie chodzi mi nawet o dane w stylu że ten algorytm ma złożoność czasową n^2 a ten n log n, tylko proste dane, że wykonywał się 2000 milisekund i zeżarł 1000 kb pamięci.

Pozostało 580 znaków

2011-03-25 21:10
0

W C++ masz

 GetTime(); 

Jednakże zwraca ona datę zegara systemowego. Więc chyba nie o to Ci chodziło.


:)
edytowany 1x, ostatnio: m.zoltowski, 2011-03-25 21:11

Pozostało 580 znaków

2011-03-25 21:14
first_try
0

Co do czasu wykonywania, możesz użyć Clock(), robisz dwie zmiennie int start = Clock(); algorytm, int end = Clock(); czas wykonywania = start - end, i będziesz miał czas wykonywania podany w ms.

Pozostało 580 znaków

2011-03-25 21:14
0

#include <ctime>

t=clock();
coś();
t=clock()-t;
//coś zajęło t/1000.0 sekund

Pozostało 580 znaków

2011-03-25 21:19
0

Może przedstawię swój problem dokładniej. Piszę projekt zaliczeniowy z laboratorium, moim tematem jest porównanie algorytmów rozwiązujących problem komiwojażera.
Chciałem przedstawić w jakiś schematyczny sposób ile czasu zajmuje komputerowi uporanie się z poszczególnymi algorytmami. Nie musi to być ani specjalnie skomplikowane, ani dokładne, po prostu chciałbym mieć udowodnione, że dla dużej ilości danych algorytm genetyczny jest szybszy od brutal force.

ps Sorry za niezbyt dokładne trzymanie się terminologii, ale to nigdy nie było moją mocną stroną.
ps2 wiem co to maszyna Turinga, niestety dla siebie aż za dobrze.

@ dzięki, nie zauważyłem, że podaliście odpowiedź, przez ten czas, pisałem posta.
małe pytanko - jakiego typu powinna być zmienna t ?

Można w analogiczny sposób policzyć użytą pamięć ?

edytowany 2x, ostatnio: mefist665, 2011-03-25 21:22

Pozostało 580 znaków

2011-03-25 21:39
0

Typ std::clock_t, funkcja std::clock() - z ctime.

// w sekundach:
(start - stop) / (double)CLOCKS_PER_TICK

edytowany 1x, ostatnio: Xupicor, 2011-03-25 21:41

Pozostało 580 znaków

2011-03-25 21:43
0
#include <time.h>
...
t_time start, end;
time(&start)
...
time(&end)
...
difftime(end,start);

Pozostało 580 znaków

2011-03-30 02:00
hmmm..
0

co do pamieci, to mozesz np. utworzyc klase trzymajaca dany typ (czy to int czy inny), ale dodac w jej konstruktorach i destruktorach jakis mechanizm liczacy ile instancji danej klasy jest w danym momencie utworzonych. Bedzie i narzut czasowy i pamieciowy ale pi razy oko mozesz porownac, ze dany algorytm potrzebowal x% wiecej pamieci niz inny.

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