Wyobraź sobie, że masz napisać program, który przeszukuje listę liczb i znajduje największą. Napiszesz kod, przetestujesz go, działa! Ale co się stanie, jeśli zamiast 10 liczb podasz 10 milionów?
Tu właśnie pojawia się pytanie: czy Twój algorytm nadal będzie działał wystarczająco szybko? A jeśli masz kilka rozwiązań – które będzie bardziej efektywne?
Odpowiedź kryje się w pojęciu złożoności obliczeniowej.
Czym jest złożoność obliczeniowa?
Złożoność obliczeniowa to sposób oceny efektywności algorytmu – czyli tego, jak bardzo rosną jego wymagania (czas, pamięć) w zależności od wielkości danych wejściowych.
Mamy dwa główne rodzaje:
- Złożoność czasowa – jak długo działa algorytm?
- Złożoność pamięciowa – ile pamięci (RAM) potrzebuje?
I to nie w sekundach czy megabajtach – tylko w kategoriach matematycznych, takich jak O(n), O(n^2), O(log n) itd.
Dlaczego nie mierzymy złożoności w sekundach?
Bo sekundy zależą od:
- komputera (procesor, RAM),
- języka programowania,
- optymalizacji kompilatora,
- itd.
Złożoność obliczeniowa opisuje zależność algorytmu od wielkości wejścia, a nie od środowiska, w którym działa. To taki pomiar niezależny od sprzętu.
Notacja Big-O (O-notation)
To sposób zapisu, który pokazuje jak szybko rosną zasoby potrzebne algorytmowi w zależności od liczby elementów n (czyli np. liczby danych do przetworzenia).
Przykłady:
- O(1) – czas stały: nie zależy od wielkości danych
- O(n) – czas liniowy: rośnie proporcjonalnie do liczby danych
- O(n^2) – czas kwadratowy: rośnie szybciej niż dane
- O(log n) – logarytmiczny: bardzo szybki wzrost, typowy dla przeszukiwania
- O(n log n) – np. szybkie sortowanie
- O(2^n) – eksponencjalny, bardzo kosztowny
Czas na bardziej jasne przykłady
O(1) – stały czas
Masz pudełko i chcesz sprawdzić, czy coś w nim jest. Zaglądasz i od razu wiesz. Nie ma znaczenia, ile razy zaglądasz – to zawsze ten sam czas.
def get_first_element(lst):
return lst[0]
Code language: Python (python)
O(n) – liniowy czas
Przeglądasz listę gości na imprezie i sprawdzasz, czy Twój znajomy się zapisał. Musisz przejść przez wszystkich – im więcej osób, tym dłużej.
def find_name(name, guest_list):
for guest in guest_list:
if guest == name:
return True
return False
Code language: Python (python)
O(n²) – kwadratowy czas
Każdego gościa pytasz o wszystkich innych gości: „czy się znacie?”. W efekcie masz n * n porównań.
def find_duplicates(lst):
for i in range(len(lst)):
for j in range(i + 1, len(lst)):
if lst[i] == lst[j]:
return True
return False
Code language: Python (python)
O(log n) – logarytmiczny czas
Przeszukujesz książkę telefoniczną – nie od początku do końca, ale dzieląc ją na pół: „czy nazwisko jest przed czy po?”. To przeszukiwanie binarne.
def binary_search(lst, target):
low = 0
high = len(lst) - 1
while low <= high:
mid = (low + high) // 2
if lst[mid] == target:
return True
elif lst[mid] < target:
low = mid + 1
else:
high = mid - 1
return False
Code language: Python (python)
Małe porównanie
| Złożoność | Operacji |
| O(1) | 1 |
| O(log n) | ~14 |
| O(n) | 10 000 |
| O(n log n) | ~140 000 |
| O(n²) | 100 mln |
| O(2^n) | 💀 |
Wniosek? Różnice są gigantyczne!
Złożoność pamięciowa – ile RAM-u potrzebujesz?
Działa podobnie jak czasowa, tylko patrzymy na ilość danych tworzonych w trakcie działania programu.
def duplicate_list(lst):
return lst + lst # tworzy nową listę 2x większą → O(n)
Code language: Python (python)
Jak analizować złożoność?
- Zwracaj uwagę na pętle i rekurencję
- jedna pętla → O(n),
- dwie zagnieżdżone → O(n²),
- podział na pół → O(log n).
- Ignoruj stałe i słabe składniki
- O(2n + 3) to i tak O(n)
- Zwróć uwagę na zależność od danych wejściowych
- O(m * n) – dwa niezależne rozmiary
Jak wykorzystać złożoność w praktyce?
- Wybieraj odpowiednie algorytmy (np. binary_search zamiast for w liście)
- Optymalizuj tylko tam, gdzie warto – czasem O(n) wystarczy
- Znaj złożoności wbudowanych operacji (np. in w liście = O(n), ale w set() = O(1))
- Korzystaj z dokumentacji i analizuj testami dużych danych
Na studiach – bardziej formalnie (ale o tym więcej innym razem)
Na uczelni spotkasz także:
- Złożoność w notacjach Θ (theta), Ω (omega)
- Θ(n) – dokładna złożoność,
- Ω(n) – dolna granica
- O(n) – górna granica (najczęściej używana)
- Klasy złożoności (np. P, NP, NP-zupełne)
- bardziej teoretyczne, ale potrzebne np. w algorytmice i kryptografii
Podsumowanie – co zapamiętać?
- Złożoność obliczeniowa mierzy wydajność algorytmu względem danych wejściowych
- Najczęściej patrzymy na czas i pamięć
- Warto znać różnice między O(1), O(n), O(log n), O(n²)…
- Używaj złożoności jako narzędzia porównawczego, nie absolutnego miernika
- Czasem wolniejszy, ale prostszy kod jest lepszy – dopóki nie staje się problemem
