Algorytm znajdowania minimum

Algorytm znajdowania minimum służy do wyznaczenia najmniejszej wartości w zestawie danych, np. w tablicy liczb. Standardowa metoda polega na przejrzeniu wszystkich elementów i zapamiętywaniu najmniejszego dotąd znalezionego.

Zasada działania

1. Przyjmij pierwszy element jako aktualne minimum.
2. Przejdź po kolejnych elementach tablicy.
3. Jeśli aktualny element jest mniejszy od zapamiętanego minimum, zaktualizuj minimum.
4. Po zakończeniu pętli zwróć znalezioną wartość.

Przykład pseudokodu

minimum = tablica[0]

for i = 1 to n - 1:
    if tablica[i] < minimum:
        minimum = tablica[i]

return minimum

Złożoność

Dla tablicy zawierającej n elementów algorytm musi sprawdzić każdy element co najmniej raz. Wykonuje więc liczbę operacji proporcjonalną do liczby danych.

Złożoność czasowa standardowego wyszukiwania minimum wynosi:

O(n)

Nie jest to O(n²), ponieważ nie ma tu dwóch zagnieżdżonych pętli. Nie jest to też O(1), ponieważ czas działania zależy od liczby elementów.

Wniosek egzaminacyjny

Jeżeli pytanie dotyczy prostego wyszukiwania najmniejszej wartości w nieposortowanym zestawie liczb, poprawną odpowiedzią jest O(n).