Złożoność Obliczeniowa (Notacja O)

W Części Zadaniowej Matury z Informatyki niemal zawsze pada pytanie: "Podaj (lub oszacuj) złożoność czasową swojego algorytmu". Czym jest złożoność? To nie jest czas mierzony w sekundach! Komputer w NASA policzy to szybciej niż 10-letni laptop. Złożoność odpowiada na pytanie: Jak zachowa się mój algorytm, gdy dorzucę mu milion razy więcej danych (n)?

Zamiast pisać matematyczne referaty, opisujemy to przy pomocy tak zwanej Notacji O (Omikron / Big O). Odrzuca ona stałe i skupia się na najgorszym scenariuszu.

1. O(1) - Złożoność Stała (Strzała)

Najszybsza możliwa rzecz. Czas działania w ogóle nie zależy od tego, jak duże są dane (od n).

• Przykład: Sprawdzenie, czy pierwsza liczba na początku milionelementowej listy jest parzysta. Czy mam listę 5 elementów, czy 5 miliardów, wykonuję tylko jedną, błyskawiczną operację. czas = stały.

2. O(n) - Złożoność Liniowa (Przegląd)

Czas działania rośnie dokładnie tak samo szybko jak dane.

• Przykład: Znalezienie największej liczby w nieposortowanej liście (lub wyszukiwanie liniowe). Jeśli masz 10 pudełek, musisz zajrzeć do 10. Jeśli masz milion pudełek, musisz sprawdzić milion.
• W Kodzie: Najczęściej objawia się to jedną pętlą FOR przechodzącą przez wszystkie dane:

for (int i = 0; i < n; i++) { ... } // Złożoność O(n)

3. O(n^2) - Złożoność Kwadratowa (Porażka dla wielkich liczb)

Uważaj! Jeśli lista rośnie 10 razy, to czas działania rośnie aż 100 razy (10^2).

• Przykład: Popularne na maturze Sortowanie Bąbelkowe (Bubble Sort).
• W Kodzie: Zazwyczaj objawia się to pętlą w pętli (Zagnieżdżenie). Zewnętrzna pętla kręci się n razy, a wewnętrzna znów n razy dla każdego kroku zewnętrznej. n * n = n^2.

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        // Tu zrobisz coś n * n razy! -> O(n^2)
    }
}

4. O(log n) - Złożoność Logarytmiczna (Geniusz) 🪤

Ukochana przez egzaminatorów i programistów struktura. Mimo że danych przybywa, czas działania rośnie bardzo, bardzo powoli.

• Przykład: Wyszukiwanie Binarne w posortowanym zbiorze! Szukając słowa w słowniku, otwierasz go w połowie. Jeśli słowo jest dalej, odrzucasz całą lewą połowę w ułamku sekundy. Mając milion haseł, nie musisz sprawdzać miliona, odrzucasz od razu 500 000! Następnym cięciem odrzucasz 250 000. Z miliona rekordów dochodzisz do wyniku w zaledwie 20 krokach!
• W Kodzie: Zazwyczaj objawia się to pętlą while, w której n jest w każdym kroku dzielone przez 2 (lub gdy w rekurencji wywołujesz tylko połówkę zbioru).

Maturalny Tip: Jeśli masz zadanie, w którym dzielisz wielką liczbę cyfra po cyfrze używając liczba / 10 (np. by zsumować jej cyfry), lub tniesz tablicę o połowę (jak w wyszukiwaniu binarnym), jest to ogromna flaga sygnalizująca, że złożoność wynosi O(log n) lub w połączeniu z inną operacją O(n log n).