Algorytm "naiwnego" wyszukiwania minimum polega na wykonaniu jednego pełnego przejścia po danych. Typowy przebieg wygląda tak: ustawiasz pierwszy element jako aktualne minimum, a następnie dla każdego kolejnego elementu sprawdzasz (porównujesz), czy jest mniejszy i ewentualnie aktualizujesz zapamiętaną wartość.
Klucz do oceny złożoności to policzenie, ile razy wykonuje się operacja zależna od liczby elementów n. Dla wejścia o rozmiarze n wykonujesz około n−1 porównań (dla każdego elementu poza pierwszym). Aktualizacja minimum, przypisania i odczyty to operacje stałokosztowe, które nie zmieniają rzędu wzrostu.
Dlatego całkowity czas działania rośnie liniowo wraz z n i zapisuje się go jako O(n). Nie ma tu zagnieżdżonych pętli po n, nie porównujesz każdej pary elementów, tylko każdy element porównujesz z bieżącym minimum.
Dlaczego pozostałe odpowiedzi są błędne?
- O(n^2) opisuje sytuacje, gdy wykonujesz zagnieżdżone iteracje po danych (np. porównujesz każdą parę elementów) albo wielokrotnie przeglądasz całą listę. W szukaniu minimum nie jest to potrzebne.
- O(n^3) dotyczy jeszcze głębszych zagnieżdżeń (trzech pętli) i w praktyce pojawia się w wybranych algorytmach grafowych lub w naiwnych algorytmach na macierzach. Tu nie występuje.
- O(n!) jest typowe dla problemów przeszukiwania permutacji i bruteforce (np. niektóre warianty problemu komiwojażera). Szukanie minimum nie wymaga rozważania permutacji elementów.
Wskazówka egzaminacyjna: jeśli w pseudokodzie widzisz jedną pętlę przechodzącą po n elementach i w środku tylko proste instrukcje (porównanie, przypisanie), najczęściej będzie to O(n).
