Złożoność obliczeniowa - notacja Big O
1. Czym jest złożoność obliczeniowa?
Złożoność obliczeniowa to miara wydajności algorytmu, która określa, jak szybko rośnie czas wykonania lub zużycie pamięci w zależności od rozmiaru danych wejściowych.
Dlaczego to ważne?
- Pozwala porównywać algorytmy niezależnie od sprzętu czy języka programowania.
- Pomaga przewidzieć wydajność dla dużych zbiorów danych.
- Umożliwia optymalizację kodu przez wybór lepszego algorytmu.
2. Notacja Big O – podstawy
Notacja Big O (O – od "Order of") opisuje górne ograniczenie czasu wykonania algorytmu w najgorszym przypadku.
Ogólna postać:
O(f(n))
Gdzie: * n – rozmiar danych wejściowych * f(n) – funkcja opisująca liczbę operacji
Przykład intuicyjny:
Jeśli algorytm ma złożoność O(n), oznacza to, że dla 10 elementów wykona około 10 operacji, a dla 1000 elementów około 1000 operacji.
3. Najczęstsze klasy złożoności
| Notacja | Nazwa | Opis | Przykład |
|---|---|---|---|
| O(1) | Stała | Czas wykonania nie zależy od rozmiaru danych | Dostęp do elementu tablicy |
| O(log n) | Logarytmiczna | Rośnie bardzo wolno | Wyszukiwanie binarne |
| O(n) | Liniowa | Rośnie proporcjonalnie do n | Przeszukiwanie listy |
| O(n log n) | Liniowo-logarytmiczna | Typowa dla efektywnych algorytmów sortowania | Merge Sort, Quick Sort |
| O(n²) | Kwadratowa | Rośnie bardzo szybko | Sortowanie bąbelkowe |
| O(n³) | Sześcienna | Bardzo wolna dla dużych danych | Mnożenie macierzy (naiwne) |
| O(2ⁿ) | Wykładnicza | Nieużyteczna dla większych n | Rekurencyjne Fibonacci |
| O(n!) | Silnia | Praktycznie nieużyteczna | Wszystkie permutacje |
4. Wizualizacja wzrostu złożoności
Przyjmijmy, że jedna operacja zajmuje 1 mikrosekundę:
| n | O(1) | O(log n) | O(n) | O(n log n) | O(n²) | O(2ⁿ) |
|---|---|---|---|---|---|---|
| 10 | 1 µs | 3 µs | 10 µs | 33 µs | 100 µs | 1 ms |
| 100 | 1 µs | 7 µs | 100 µs | 664 µs | 10 ms | 4×10¹³ lat |
| 1000 | 1 µs | 10 µs | 1 ms | 10 ms | 1 s | – |
Jak widać, wybór algorytmu ma kolosalne znaczenie dla dużych zbiorów danych!
5. O(1) – Złożoność stała
Algorytm wykonuje stałą liczbę operacji niezależnie od rozmiaru danych.
Przykład: Dostęp do elementu listy
Złożoność: O(1) – zawsze wykonujemy jedną operację.
Przykład: Sprawdzanie, czy klucz istnieje w słowniku
6. O(log n) – Złożoność logarytmiczna
Algorytm dzieli problem na pół w każdym kroku.
Przykład: Wyszukiwanie binarne
Złożoność: O(log n) – w każdej iteracji odrzucamy połowę elementów.
Porównanie: - Dla 1000 elementów: wyszukiwanie liniowe – 1000 kroków, binarne – ~10 kroków. - Dla 1 000 000 elementów: liniowe – 1 000 000 kroków, binarne – ~20 kroków.
7. O(n) – Złożoność liniowa
Algorytm przetwarza każdy element dokładnie raz.
Przykład: Suma elementów listy
Złożoność: O(n) – dla n elementów wykonujemy n operacji.
Przykład: Wyszukiwanie liniowe
Złożoność: O(n) – w najgorszym przypadku sprawdzamy wszystkie elementy.
8. O(n log n) – Złożoność liniowo-logarytmiczna
Typowa dla efektywnych algorytmów sortowania.
Przykład: Sortowanie przez scalanie (Merge Sort)
Złożoność: O(n log n) – dzielimy listę log n razy, a każde scalanie to O(n).
9. O(n²) – Złożoność kwadratowa
Algorytm używa zagnieżdżonych pętli przeglądających dane.
Przykład: Sortowanie bąbelkowe
Złożoność: O(n²) – zewnętrzna pętla: n iteracji, wewnętrzna: n iteracji → n × n = n².
Przykład: Sprawdzanie duplikatów (naiwne podejście)
Złożoność: O(n²)
Lepsze rozwiązanie (O(n)):
10. O(2ⁿ) – Złożoność wykładnicza
Każdy dodatkowy element podwaja czas wykonania.
Przykład: Rekurencyjne Fibonacci (niewydajne)
Złożoność: O(2ⁿ) – drzewo wywołań rośnie wykładniczo.
Problem: - fibonacci(40) – kilka sekund - fibonacci(50) – kilka minut - fibonacci(100) – praktycznie niemożliwe
Lepsze rozwiązanie (O(n)) z memoizacją:
11. Zasady analizy Big O
Reguła 1: Ignoruj stałe
Reguła 2: Dominujący składnik
Reguła 3: Różne zmienne
Reguła 4: Zagnieżdżone pętle na różnych danych
12. Najlepszy, średni i najgorszy przypadek
Algorytmy mogą mieć różną złożoność w zależności od danych:
Przykład: Quick Sort
Złożoność Quick Sort: - Najgorszy przypadek: O(n²) – gdy pivot jest zawsze skrajny - Średni przypadek: O(n log n) - Najlepszy przypadek: O(n log n)
13. Praktyczne wskazówki
Jak rozpoznać złożoność algorytmu?
- Jedna pętla przez n elementów → O(n)
- Dwie zagnieżdżone pętle → O(n²)
- Dzielenie problemu na pół → O(log n)
- Dzielenie + przetwarzanie wszystkich → O(n log n)
- Rekurencja z dwoma wywołaniami → często O(2ⁿ)
Przykłady z Pythona:
14. Podsumowanie
Notacja Big O jest kluczowa dla zrozumienia wydajności algorytmów:
- O(1), O(log n), O(n) – efektywne algorytmy
- O(n log n) – akceptowalne dla sortowania
- O(n²), O(2ⁿ), O(n!) – unikać dla dużych zbiorów danych
Co dalej warto poznać:
- Złożoność pamięciowa (Space Complexity)
- Analiza najlepszego, średniego i najgorszego przypadku
- Notacja Omega (Ω) i Theta (Θ)
- Praktyczne porównanie algorytmów sortowania i wyszukiwania
- Techniki optymalizacji (memoizacja, programowanie dynamiczne)