Czym jest złożoność obliczeniowa?
Złożoność obliczeniowa opisuje, jak szybko rośnie zapotrzebowanie algorytmu na zasoby wraz ze wzrostem liczby danych wejściowych n. Najczęściej analizuje się:
- złożoność czasową - ile operacji wykonuje algorytm,
- złożoność pamięciową - ile dodatkowej pamięci potrzebuje algorytm.
W zadaniach egzaminacyjnych najczęściej chodzi o złożoność czasową zapisywaną w notacji O(...), np. O(n), O(n log n), O(n²).
Przykładowe klasy złożoności
Od zwykle najkorzystniejszej do mniej korzystnej dla dużych danych:
O(1)- czas stały, niezależny od liczby danych,O(log n)- czas logarytmiczny,O(n)- czas liniowy,O(n log n)- typowy dla wydajnych algorytmów sortowania porównawczego,O(n²)- czas kwadratowy, niekorzystny dla dużych zbiorów.
Przykład w sortowaniu
Dla dużych zbiorów danych algorytm o złożoności O(n) będzie zwykle wydajniejszy niż algorytm O(n log n), a ten będzie lepszy niż O(n²).
W pytaniu egzaminacyjnym należy więc porównać podane wartości złożoności. Skoro sortowanie przez zliczanie ma O(n), a pozostałe metody mają O(n log n) lub O(n²), to najefektywniejsze według tabeli jest sortowanie przez zliczanie.
Ważna uwaga
Notacja O(...) opisuje tempo wzrostu kosztu algorytmu, a nie dokładny czas wykonania w sekundach. W praktyce znaczenie mają też stałe, implementacja, pamięć i rodzaj danych wejściowych.