Jednoczesne wyznaczanie minimum i maksimum tablicy przy minimalnej liczbie porównań.
Znajdowanie jednocześnie minimum i maksimum w tablicy można zrealizować na dwa sposoby.
Wersja naiwna: dwa osobne przebiegi tablicy – jeden dla minimum, drugi dla maksimum. Daje to 2n porównań, czyli złożoność O(2n) (która formalnie należy do klasy O(n)).
Wersja zoptymalizowana: w jednym przebiegu śledzimy zarówno minimum, jak i maksimum. Kluczowa optymalizacja: jeśli element okazał się mniejszy od minimum, to nie może być większy od maksimum, więc drugi warunek pomijamy (stąd w przeciwnym razie jeżeli).
Różnica w praktyce: asymptotycznie ta sama złożoność, ale na dużych zbiorach mniejsza liczba porównań i jeden przebieg pamięci dają zauważalne przyspieszenie.
Na maturze: często pojawia się w zadaniach z liczeniem porównań i analizą efektywności algorytmów.
funkcja min_max(T, n): // inicjalizujemy oba ekstrema pierwszym elementem min ← T[0] max ← T[0] dla i od 1 do n - 1: jeżeli T[i] < min: min ← T[i] w przeciwnym razie jeżeli T[i] > max: max ← T[i] zwróć min, max
def min_max(tablica):
minimum = tablica[0]
maksimum = tablica[0]
for i in range(1, len(tablica)):
if tablica[i] < minimum:
minimum = tablica[i]
elif tablica[i] > maksimum:
maksimum = tablica[i]
return minimum, maksimum
# Przykład użycia
dane = [3, 1, 7, 5, 9, 2, 8]
print(min_max(dane))
# Wynik: (1, 9)O(n)O(1)Zagadnienia z tego samego obszaru matury – warto je powtórzyć razem: