O złożoności czasowej i pamięciowej programów na Olimpiadę Informatyczną

27.09.2021 O złożoności czasowej i pamięciowej programów na Olimpiadę Informatyczną

Źródło: www.freepik.com

Złożoność czasowa na Olimpiadzie Informatycznej: Wstęp

Osoby zaczynające przygotowania do Olimpiady Informatycznej często mają problemy z szacowaniem złożoności czasowej i pamięciowej swojego programu. Ten artykuł ma na celu w tym pomóc.

Kiedy wysyła się kod do sprawdzenia zadania, maszyna sprawdzająca kompiluje kod i przepuszcza go przez testy. Każdy test stanowi plik wejściowy dla naszego programu. Ma on zawsze swój limit pamięciowy i czasowy. Informacja o limicie pamięciowym zostaje zazwyczaj umieszczona w treści (na Olimpiadzie Informatycznej zawsze tam będzie). Jest taka sama dla wszystkich testów, informacja o limicie czasowym jest natomiast podawana rzadko. Choć na Olimpiadzie Informatycznej od niedawna występuje zawsze, w wysyłanych plikach z zadaniami na stronę. Przekroczenie któregokolwiek z limitów, tak samo, jak podanie złej odpowiedzi, skutkuje niezaliczeniem testu, czyli nieotrzymaniem za niego żadnych punktów. Za chwilę dowiesz się dlaczego złożoność czasowa na Olimpiadzie Informatycznej to takie ważne zagadnienie. Ten tekst jest jednym z wielu opracowań, które wchodzą w skład naszego kompleksowego kursu przygotowującego od OI! Zachęcamy do zajrzenia na zakładkę dedykowaną przygotowaniom!

Złożoność pamięciowa na Olimpiadzie Informatycznej

Złożoność pamięciowa programu wynika z zadeklarowanych przez nas zmiennych, które zajmują pamięć. W przeważającej większości zadań limity pamięciowe są duże (128MB+) i nie trzeba się nimi w ogóle przejmować. Czasami jednak zdarzają się zadania, w których musimy uważać na ten parametr. Powinno się mieć go z tyłu głowy, gdy limit pamięci to 64MB, tym bardziej, kiedy wynosi 32MB, w przypadku niższych wartości staje się główną determinantą tego, w jaki sposób należy podejść do rozwiązania zadania.

Z najpopularniejszych typów danych warto wymienić, że bool zajmuje 1 bajt, int 4 bajty, a long long 8 bajtów. Należy się przejmować jedynie tablicami – deklarując pojedyncze zmienne, a nawet tablice rozmiaru kilkudziesięciu tysięcy, nie wpływamy w żaden znaczący sposób na zużywaną przez nas pamięć. Trzeba zwracać natomiast uwagę na największe tablice przez nas deklarowane. Tablica miliona booli to 1 MB, miliona intów to 4 MB, miliona long longów to 8 MB. Wartości te można łatwo skalować – 3 miliony intów to 12  MB, pół miliona long longów to 4 MB. Warto zwrócić uwagę na wniosek wypływający z tych ustaleń – mianowicie, że tablice w naszych programach nie mogą być większe niż kilka, kilkanaście milionów zmiennych. Tablica intów o rozmiarze 100 milionów zajmowałaby 400 MB – możemy więc o niej zapomnieć.

Złożoność czasowa na Olimpiadzie Informatycznej

Złożoność czasową programów wyraża się w notacji O (big O notation). Służy ona do szacowania, jak zmienia się czas działania w zależności od wejścia. Na przykład zapis O(k*n²) sugeruje, że jeśli zwiększymy k trzykrotnie, to program będzie działał około 3 razy wolniej, a jeśli zmniejszymy n dwukrotnie, to będzie działał 4 razy szybciej.

Złożoność swojego programu sprawdzamy dla najgorszego możliwego przypadku, czyli dla sytuacji, w której występuje największe wejście z takimi wartościami, przy których nasz program robi najwięcej. Kwestię tego, ile wartości możemy wprowadzić na wejściu, a także jakiej wielkości nie powinny przekraczać i jakie typy reprezentować, należy przeczytać w treści. Tak samo, jak w przypadku złożoności pamięciowej sprawdzamy tylko najwolniejsze elementy programu. Jeśli mamy podwójną pętlę przechodzącą po n, to pojedyncza dodatkowa pętla przechodząca po n nie będzie miała znaczącego wpływu na naszą złożoność czasową.

Złożoność najprostszych programów można sprawdzić, patrząc na pętle i pętle w pętlach. Trzeba zobaczyć, w ile razy w najmniej korzystnym przypadku przez te pętle przejdzie program. Później szacowanie złożoności staje się trochę trudniejsze – trzeba pamiętać o tym, że różne funkcje, takie jak np. sort, mają własne złożoności (w przypadku sort jest to n logn, gdzie n to liczba sortowanych elementów) i własne funkcje, w tym wywoływane rekurencyjnie, mogą komplikować sprawę. Każdy olimpijczyk, poznając nowe algorytmy będzie się dowiadywał o ich czasowych złożonościach.

Jak stwierdzić podczas planowania rozwiązania, czy robimy to w dobrej złożoności?

Możemy do naszej funkcji O podstawić najgorszy przypadek wartości z zadania i policzyć wynik. Nie jest to metoda doskonała. Program mający jedną pętlę przechodzącą przez n ma taką samą złożoność w notacji O jak program, który ma tych pętli 10. Zazwyczaj jednak takie szacowanie wystarcza. Wynika to z faktu, że często różnice w czasach działania programów o różnych złożonościach będą tysiąc-, a czasami nawet milionkrotne. Testy mogą też mieć różne limity czasowe, czego zaproponowane szacowanie nie bierze pod uwagę. Złota zasada w tym przypadku mogłaby brzmieć, że jeśli po podstawieniu tych wartości do funkcji O naszego programu uzyskamy kilka, kilkanaście albo kilkadziesiąt milionów, to możemy zachować spokój.

Dzięki powyższemu szacowaniu możemy też spróbować na podstawie treści zadania określić, jakiej złożoności programu się od nas oczekuje. Jeśli na przykład widzimy w treści, że n nie może przekroczyć 1000, należy się spodziewać, że oczekiwany program będzie miał złożoność podobną do O(n²) – co może nam podpowiedzieć, jak się z nim uporać.

Złożoność czasowa na Olimpiadzie Informatycznej: Podsumowanie

Na koniec warto dodać, że zadania algorytmiczne mają często podzadania – na Olimpiadzie Informatycznej jest to sytuacja powszechna. Można je znaleźć (jeśli są) w treści zadania. Podzadania to grupy testów, które mają łatwiejsze założenia od pełnego zadania. Często oznacza to mniejsze wejście, niższe wartości na wejściu czy inne dodatkowe założenia o wejściu, jak np. to, że liczby na wejściu są parzyste, które mają ułatwić zadanie. Za podzadania dostaje się częściowe punkty, można je zrobić za pomocą programów o większej złożoności czasowej niż pełne zadanie. Punkty z podzadań nie powinny zostać przez ciebie zlekceważone! W zeszłorocznej olimpiadzie można było przejść II i III etap dostając 25 punktów (na 100 możliwych) średnio za zadanie! Często też wymyślanie rozwiązań podzadań może nas poprowadzić do rozwiązania pełnego zadania.

To już koniec naszego artykułu, którego tematem była złożoność czasowa na Olimpiadzie Informatycznej! Zachęcamy do zajrzenia na naszą zakładkę dedykowaną kompleksowemu przygotowaniu do OI!

Autor tekstu: Piotr Kępczyński

Grupa odnośnie Przygotowań do Olimpiady Informatycznej

Chcesz być ze wszystkim na bieżąco? Dołącz do grupy na Facebooku!