Wskaż złożoność obliczeniową algorytmu naiwnego (zwykłego) wyszukiwania minimum w zbiorze liczb.
A. O(n2)
B. O(n!)
C. O(n)
D. O(n3)
Pytanie z egzaminu CKE, styczeń 2021 (arkusz EE.09-SG-21.01).
Algorytm naiwny wyszukiwania minimum ma złożoność $O(n)$, ponieważ w najprostszym wariancie trzeba przejrzeć każdy element zbioru przynajmniej raz. Typowy schemat jest taki: zakładamy, że pierwszy element jest aktualnym minimum, a potem porównujemy go z każdym następnym elementem. Jeśli znajdziemy mniejszą wartość, aktualizujemy minimum. Dla 10 liczb wykonamy około 9 porównań, dla 1000 liczb około 999 porównań, czyli liczba operacji rośnie liniowo razem z rozmiarem danych. I o to właśnie chodzi w notacji dużego O: nie liczymy każdej instrukcji co do sztuki, tylko patrzymy, jak zachowuje się algorytm przy większym wejściu. W praktyce to bardzo ważne, np. przy przeszukiwaniu tablicy wyników, listy cen w sklepie internetowym albo danych pobranych z bazy. Moim zdaniem to jeden z najprostszych, ale też najbardziej przydatnych przykładów analizy algorytmów. Dobra praktyka programistyczna mówi, żeby rozumieć koszt pętli po danych, bo potem łatwiej ocenić, czy rozwiązanie będzie działało sensownie dla większych zbiorów.
Wyszukiwanie minimum w zwykłym, naiwnym podejściu nie wymaga zagnieżdżonych pętli ani sprawdzania wszystkich możliwych kombinacji elementów. Wystarczy jedno przejście po zbiorze liczb, więc czas działania rośnie liniowo wraz z liczbą elementów. Jeśli ktoś wybiera $O(n^2)$, to najczęściej myli ten problem z algorytmami, w których porównuje się wiele par elementów, na przykład w prostych metodach sortowania typu sortowanie bąbelkowe. Tam rzeczywiście mogą wystąpić dwie pętle i liczba operacji rośnie znacznie szybciej, ale samo znalezienie najmniejszej wartości tego nie potrzebuje. Złożoność $O(n^3)$ pasuje raczej do algorytmów z trzema zagnieżdżonymi pętlami, np. niektórych naiwnych obliczeń na macierzach albo sprawdzania trójek elementów. Tutaj nie ma żadnego powodu, aby każdy element porównywać z wieloma innymi w tak rozbudowany sposób. Jeszcze bardziej przesadzone jest $O(n!)$, które pojawia się przy problemach permutacyjnych, gdzie rozważamy wszystkie możliwe kolejności, jak w naiwnym podejściu do problemu komiwojażera. Przy szukaniu minimum nie układamy liczb w każdej możliwej konfiguracji, tylko przechodzimy po nich po kolei. Typowy błąd myślowy polega na tym, że słowo naiwny kojarzy się od razu z czymś bardzo wolnym. A to nie zawsze prawda. Naiwny algorytm może być prosty i jednocześnie optymalny czasowo, tak jak w tym przypadku, bo żeby mieć pewność, że znamy minimum, trzeba obejrzeć wszystkie elementy przynajmniej raz.