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

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.

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

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.

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.

0

W C++ masz

 GetTime(); 

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

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.

0

#include <ctime>

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

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

0

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

// w sekundach:
(start - stop) / (double)CLOCKS_PER_TICK
0
#include <time.h>
...
t_time start, end;
time(&start)
...
time(&end)
...
difftime(end,start);
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.

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