--> Archiwum Forum
master53 [ Senator ]
Olimpiada informatyczna - wyliczanie zapotrzebowania pamięci oraz czasu ...
W konkursach typu OI, w każdym zadaniu podawany jest limit pamięci oraz limit czasu, przez który mają trwać obliczenia. Np. zadanie:
Limit pamięci: 32 MB, limit czasu 1 sekunda. W jaki sposób mogę sprawdzić czy mój program nie przekracza którejś z wartości ? Czy są jakieś narzędzia do tego ?
GBreal.II [ floydian ]
Co do pamieci:
Masz podane maksymalne wartosci kazdej zmiennej, wiec masz pewnie jakies tablice jakis typow. Int na przyklad zajmuje zwykle 4 bajty (do sprawdzenia ilosci zajmowanego miejsca jest funkcja sizeof(type), torra zwraca ilosc miejsca zajmowanego przez jedna zmienna podanego typu w bajtach. Mnozysz to razy pojemnosc zadeklarowanych tabilc, sumujesz wszystkie tablice, pamietasz o pewnym marginesie na pozostale zmnienne i masz ilosc miejsca zajmowanego przez program
master53 [ Senator ]
No tak, można ręcznie to liczyć, tylko czy jest jakiś automat zliczający to sam ? Tak samo jeśli chodzi o czas.
diabelek1 [ szczęśliwy ]
Czas raczej trudno policzyc, bo zalezy od konkretnej maszyny...
DEXiu [ Generaďż˝ ]
No tak, można ręcznie to liczyć, tylko czy jest jakiś automat zliczający to sam ? Tak samo jeśli chodzi o czas.
Dodawać nie umiesz, a na OI się porywasz? ;) Szacunkowo chyba dość łatwo pomnożyć np. 1000000*4 B i dodać do tego jeszcze kilka podobnych wartości? Co do czasu - niezależnie od maszyny powinieneś przyjąć, że jeśli czas wykonania dla najgorszego zestawu danych (najbardziej pesymistyczne założenie - mogą to być np. maksymalne dane, choć niekoniecznie) mierzony jest w sekundach (a już zwłaszcza klikunastu bądź kilkudziesięciu), to należałoby coś poprawić. Generalnie dobrze jest umieć oszacować sobie złożoność obliczeniową: logarytmiczna - idealnie, liniowa - bardzo dobrze, liniowo-logarytmiczna - nieźle, kwadratowa - tak sobie, potęgowa - kiepsko, wykładnicza - tragedia. To w dużym uproszczeniu :)
BIGos [ bigos?! ale głupie ]
w języku C są takie funkcje jak time() i difftime() - mozesz je wykorzystac.
Scatterhead [ łapaj dzień ]
złożonośc algorytmów szacuje się w notacji O
master53 [ Senator ]
Znalazłem już odpowiednie narzędzie. Sorry za zamieszanie.
EOT.
darek_dragon [ 42 ]
Możesz spać spokojnie. Żadne zadanie na poziomie olimpiady informatycznej nie powinno zająć więcej niż kilkanaście kilobajtów pamięci i na współczesnej maszynie wykonywać się dłużej niż kilkaset milisekund :)
GBreal.II [ floydian ]
logarytmiczna - idealnie, liniowa - bardzo dobrze, liniowo-logarytmiczna - nieźle, kwadratowa - tak sobie, potęgowa - kiepsko, wykładnicza - tragedia. To w dużym uproszczeniu :)
Chyba jednak az za duzym. Nie mozna pisac ze jakas zlozonosc jest tylko "dobra", w oderwaniu od problemu, ktory rozwazamy. Bo chyba nie powiesz, ze sortowanie przez porownywanie zrobione w theta_duze(nlogn) to zaledwie "nieźle"...