Jak ocenić złożoność obliczeniową algorytmu?

Zacznijmy od prostego pytania

Wyobraź sobie, że masz szukać numeru telefonu w książce telefonicznej. Możesz to zrobić na dwa sposoby:

Przeglądasz stronę po stronie od początku — może trafisz szybko, może będziesz szukać godzinę.
Otwierasz książkę w połowie, sprawdzasz czy szukane nazwisko jest wcześniej czy później, i tak zawężasz zakres — znajdujesz numer w kilkanaście sekund.

Oba sposoby działają. Ale jeden jest o wiele mądrzejszy. Właśnie o tym mówi złożoność obliczeniowa — o tym, jak bardzo sprytny jest nasz algorytm i ile pracy musi wykonać, żeby rozwiązać problem.

Co to jest algorytm?

Algorytm to po prostu przepis na rozwiązanie zadania. Tak jak przepis kulinarny mówi krok po kroku, co zrobić, żeby upiec ciasto — algorytm mówi komputerowi krok po kroku, co zrobić, żeby posortować listę, znaleźć słowo albo obliczyć wynik.

Każdy algorytm, żeby działać, potrzebuje dwóch rzeczy:

Czasu — czyli operacji, które musi wykonać procesor.
Pamięci — czyli miejsca w RAM-ie, gdzie przechowuje dane w trakcie pracy.

Złożoność obliczeniowa to sposób na zmierzenie, ile tego czasu i pamięci potrzeba — i co ważne, jak ta ilość rośnie, gdy danych jest coraz więcej.

Dlaczego „jak rośnie” jest ważniejsze niż „ile wynosi”?

Porównajmy dwóch uczniów, którzy sprzątają klasę. Uczeń A sprząta każdą ławkę po kolei — im więcej ławek, tym więcej czasu. Uczeń B zawsze sprawdza tylko jedną konkretną ławkę, bo wie dokładnie gdzie szukać — czas jest taki sam niezależnie od liczby ławek.

Dla 10 ławek różnica jest mała. Ale dla 1000 ławek — uczeń A będzie pracował 100 razy dłużej niż przy 10 ławkach, a uczeń B nadal tyle samo. To właśnie jest sedno złożoności obliczeniowej: jak bardzo rośnie czas pracy, gdy rośnie ilość danych.

💡 Kluczowe pojęcie: Rozmiar danych wejściowych oznaczamy literą n. Może to być liczba elementów na liście, liczba uczniów w bazie, liczba słów w tekście — cokolwiek, co opisuje „jak dużo mamy do przerobienia”.

Notacja dużego O — jak zapisujemy złożoność?

Matematycy i programiści wymyślili specjalny skrót do opisywania złożoności. Nazywa się notacja dużego O i wygląda tak: O(coś). To „coś” w nawiasie mówi nam, jak szybko rośnie liczba operacji.

Nie musisz zapamiętywać wzorów — zapamiętaj obrazek. Wyobraź sobie, że n to liczba uczniów w szkole, a ty szukasz jednego z nich:

Zapis	Co to znaczy po ludzku	Przykład z życia
O(1)	Zawsze tyle samo, niezależnie od n	Znasz numer szafki ucznia — otwierasz ją od razu
O(log n)	Bardzo wolno rosnące — przy 1000 elementach tylko ~10 kroków	Szukasz w dzienniku alfabetycznym — otwierasz w połowie i zawężasz
O(n)	Rośnie tyle samo co n — 2× więcej danych = 2× więcej pracy	Pytasz każdego ucznia po kolei: „czy to ty?”
O(n²)	Rośnie bardzo szybko — 2× więcej danych = 4× więcej pracy	Każdy uczeń przedstawia się każdemu innemu uczniowi
O(2ⁿ)	Rośnie błyskawicznie — dla n=50 to więcej operacji niż atomów we Wszechświecie	Sprawdzasz wszystkie możliwe grupy z n uczniów

📌 Zapamiętaj tę kolejność — od najlepszego do najgorszego:
O(1) → O(log n) → O(n) → O(n²) → O(2ⁿ)

Jak w praktyce ocenić złożoność? — 3 proste kroki

Krok 1: Zapytaj — co jest naszym „n”?

Zanim cokolwiek policzysz, zastanów się: co rośnie, gdy problem staje się większy? Jeśli mamy listę 100 uczniów — n = 100. Jeśli jutro przyjdzie 200 uczniów — n = 200. To właśnie nasze n.

Krok 2: Policz pętle

Najprościej patrzyć na pętle w kodzie — to one wykonują pracę wielokrotnie:

Jedna pętla od 1 do n → złożoność O(n) — algorytm przegląda każdy element raz.
Dwie pętle jedna w drugiej (zagnieżdżone) → złożoność O(n²) — dla każdego elementu przeglądamy wszystkie pozostałe.
Pętla, która za każdym razem dzieli zakres na pół → złożoność O(log n) — np. szukanie binarne.

Krok 3: Weź najgorszy scenariusz

Mówimy o tym, co się stanie w najgorszym przypadku. Szukasz klucza w 10 szufladach — w najlepszym razie jest w pierwszej, w najgorszym w ostatniej. Nas interesuje właśnie ten ostatni przypadek, bo planujemy na wszelką ewentualność.

Przykłady — zobaczymy to na żywym kodzie

Przykład 1 — Szukanie po kolei: O(n)

Chcemy sprawdzić, czy liczba 7 jest na liście. Sprawdzamy każdy element po kolei:

for i in range(n):
    if lista[i] == 7:
        return i   # znaleźliśmy!

Jeśli lista ma 10 elementów — sprawdzamy maksymalnie 10 razy. Jeśli ma 1000 — sprawdzamy maksymalnie 1000 razy. Praca rośnie dokładnie tak samo jak n. Złożoność: O(n).

Przykład 2 — Szukanie binarne: O(log n)

To mądrzejszy sposób — ale działa tylko na posortowanej liście. Otwieramy listę w połowie i sprawdzamy: nasza liczba jest przed tym miejscem czy za nim? Odrzucamy połowę i szukamy dalej tylko w odpowiedniej części:

lewy = 0
prawy = n - 1

while lewy <= prawy:
    środek = (lewy + prawy) // 2

    if lista[środek] == 7:
        return środek        # znaleźliśmy!
    elif lista[środek] < 7:
        lewy = środek + 1    # szukamy w prawej połowie
    else:
        prawy = środek - 1   # szukamy w lewej połowie

Dla listy 1000 elementów — wystarczy zaledwie 10 kroków (bo 2¹⁰ = 1024). Dla listy miliona elementów — tylko 20 kroków. To ogromna różnica! Złożoność: O(log n).

Przykład 3 — Sortowanie bąbelkowe: O(n²)

Porównujemy sąsiadujące elementy i zamieniamy je miejscami, jeśli są w złej kolejności. Robimy to wielokrotnie, aż cała lista będzie posortowana:

for i in range(n):
    for j in range(n - i - 1):
        if lista[j] > lista[j + 1]:
            lista[j], lista[j+1] = lista[j+1], lista[j]

Mamy pętlę w pętli. Zewnętrzna powtarza się n razy, wewnętrzna też do n razy — łącznie wykonujemy około n × n = n² porównań. Dla 100 elementów to 10 000 operacji. Dla 1000 elementów — już milion. Złożoność: O(n²).

A co ze złożonością pamięciową?

Poza czasem liczy się też to, ile miejsca w pamięci zajmuje algorytm podczas pracy. Zasada jest taka sama — patrzymy jak ta ilość rośnie wraz z n:

O(1) — algorytm używa tylko kilku zmiennych pomocniczych, niezależnie od rozmiaru danych. Przykład: sortowanie bąbelkowe — zamienia elementy na miejscu, bez dodatkowej tablicy.
O(n) — algorytm tworzy dodatkową tablicę tak samo dużą jak dane wejściowe. Przykład: sortowanie przez scalanie (Merge Sort) — musi gdzieś trzymać tymczasowe kopie danych.

⚖️ Ciekawostka: Często szybszy algorytm zajmuje więcej pamięci, a algorytm oszczędny w pamięci jest wolniejszy. To klasyczny kompromis w informatyce — wymieniamy jeden zasób na drugi.

Najczęstsze błędy — czego nie robić

Nie ignoruj pętli wewnętrznych. Jeśli jedna pętla wywołuje funkcję, która sama ma pętlę — musisz pomnożyć złożoności, nie dodać.
Nie myśl, że O(log n) to prawie tyle samo co O(n). To ogromna różnica. Dla miliona elementów: O(log n) to 20 operacji, O(n) to milion operacji.
Nie zapominaj o rekurencji. Funkcja, która wywołuje siebie samą, zajmuje pamięć na tzw. stosie wywołań. Zbyt głęboka rekurencja może „wysadzić" program błędem przepełnienia stosu.

Krótka ściągawka — kiedy jaki algorytm jest OK?

Rozmiar danych n	Akceptowalna złożoność
Do 100	Cokolwiek — nawet O(n²) lub O(2ⁿ)
Do 10 000	O(n²) jeszcze ujdzie
Do 1 000 000	Potrzebujemy O(n log n) lub lepiej
Powyżej miliarda	Tylko O(n) lub O(log n)

Podsumowanie — co zapamiętać?

Złożoność obliczeniowa mówi nam, jak bardzo rośnie ilość pracy, gdy zwiększamy ilość danych. Nie oceniamy algorytmu na jednym komputerze — oceniamy go matematycznie, żeby wiedzieć, czy sprawdzi się też przy ogromnych danych.

Trzy rzeczy, które musisz zapamiętać:

Litera n oznacza rozmiar danych wejściowych.
Notacja O(…) mówi, jak szybko rośnie czas lub pamięć w najgorszym przypadku.
Hierarchia: O(1) jest najlepsze, O(n!) najgorsze. Im niżej w tej drabinie, tym wolniejszy algorytm przy dużych danych.

Następnym razem, gdy napiszesz pętlę — zatrzymaj się na chwilę i zapytaj siebie: a co jeśli danych będzie nie 10, ale milion? To właśnie myślenie w kategoriach złożoności obliczeniowej.

Was this helpful?

0 / 0

Post Views: 30