Złożoność obliczeniowa (Big O Notation)

Co to jest złożoność obliczeniowa?

Złożoność obliczeniowa to formalna miara wydajności algorytmu. Określa, jak szybko rośnie czas wykonania (złożoność czasowa) lub zapotrzebowanie na pamięć operacyjną (złożoność pamięciowa) w funkcji rozmiaru danych wejściowych n.

Najczęstsze klasy złożoności czasowej (od najszybszych):

1. O(1) – stała: Czas wykonania nie zależy od liczby danych (np. dostęp do elementu tablicy po indeksie: arr[0], operacja push na stosie).
2. O(log n) – logarytmiczna: Z każdym krokiem przestrzeń poszukiwań zmniejsza się o połowę (np. wyszukiwanie binarne w posortowanej tablicy).
3. O(n) – liniowa: Czas rośnie proporcjonalnie do liczby elementów (np. przeszukanie liniowe tablicy, pojedyncza pętla for).
4. O(n log n) – liniowo-logarytmiczna: Optymalna złożoność dla algorytmów sortowania przez porównania (np. Quicksort, Merge sort, Heapsort).
5. O(n²) – kwadratowa: Czas rośnie proporcjonalnie do kwadratu danych wejściowych – podwójnie zagnieżdżona pętla (np. sortowanie bąbelkowe, sortowanie przez wstawianie/wybieranie).
6. O(2ⁿ) – wykładnicza: Liczba operacji podwaja się przy każdym nowym elemencie (np. naiwna rekurencja dla ciągu Fibonacciego).

Pułapki na egzaminie INF.04:

• Jeśli algorytm wykonuje podwójną pętlę for (i = 0; i < n; i++) for (j = 0; j < n; j++), jego złożoność to O(n²).
• Wykonanie dwóch niezależnych pętli po n to O(n + n) = O(2n) = O(n), a nie O(n²)!