Czym jest złożoność obliczeniowa?
Złożoność obliczeniowa opisuje, jak zmienia się czas działania algorytmu albo zużycie pamięci w zależności od rozmiaru danych wejściowych. Najczęściej oznacza się ją notacją O(...), np. O(n), O(n²), O(log n).
W egzaminach najczęściej chodzi o złożoność czasową, czyli liczbę podstawowych operacji wykonywanych przez algorytm.
Poszukiwanie minimum w kolekcji
Algorytm naiwny szukania minimum działa bardzo prosto:
- przyjmuje pierwszy element jako aktualne minimum,
- przechodzi po kolejnych elementach,
- porównuje każdy element z aktualnym minimum,
- jeśli znajdzie mniejszy, zapamiętuje go jako nowe minimum.
Przykład pseudokodu:
min = tablica[0]
dla i od 1 do n-1:
jeśli tablica[i] < min:
min = tablica[i]
Dla kolekcji zawierającej n liczb algorytm musi sprawdzić każdy element, ponieważ minimum może znajdować się na końcu. Liczba porównań rośnie więc liniowo wraz z liczbą elementów.
Wniosek egzaminacyjny
Złożoność zwykłego, naiwnego algorytmu poszukiwania minimum wynosi:
O(n)
Nie jest to O(n²), ponieważ nie występują dwie zagnieżdżone pętle po wszystkich elementach. Nie jest to też O(1), ponieważ czas działania zależy od liczby danych.