Złożoność obliczeniowa

Słownik kwalifikacji INF.04 - Projektowanie, programowanie i testowanie aplikacji

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

Złożoność obliczeniowa opisuje, jak szybko rośnie liczba operacji wykonywanych przez algorytm wraz ze wzrostem rozmiaru danych wejściowych, zwykle oznaczanego jako n.

Najczęściej używa się zapisu O(...), czyli notacji dużego O. Nie podaje ona dokładnej liczby instrukcji, ale pokazuje tempo wzrostu czasu działania algorytmu dla dużych danych.

Przykładowe złożoności

  • O(1) - czas stały, niezależny od liczby danych
  • O(log n) - czas logarytmiczny, np. wyszukiwanie binarne
  • O(n) - czas liniowy, np. przejście po całej tablicy
  • O(n log n) - typowe dla szybkich algorytmów sortowania, np. merge sort
  • O(n²) - czas kwadratowy, np. bubble sort w typowej wersji

Co oznacza O(n²)?

Złożoność O(n²) oznacza, że liczba operacji rośnie w przybliżeniu proporcjonalnie do kwadratu liczby elementów. Jeśli liczba danych wzrośnie 10 razy, liczba operacji może wzrosnąć około 100 razy.

Przykładem jest Bubble Sort, który wielokrotnie porównuje sąsiednie elementy i zamienia je miejscami. Dla wielu elementów wymaga wielu przejść po tablicy.

Przykład porównania

Dla pytania egzaminacyjnego:

  • Binary Search - O(log n)
  • Merge Sort - O(n log n)
  • Bubble Sort - O(n²)
  • Dijkstra - zależy od implementacji i struktury danych

Dlatego algorytmem o złożoności O(n²) jest Bubble Sort.