I_R_W14_M25_Java Szukanie jednoczesne min‑max
Algorytm jednoczesnego znajdowania minimum i maksimum w wersji optymalnej to świetny przykład na to, jak prosty zabieg logiczny — porównywanie elementów parami — pozwala zaoszczędzić około 25% operacji porównania w stosunku do metody naiwnej.
Poniżej znajdziesz implementację Twojego pseudokodu w języku Java, dostosowaną do standardowego indeksowania tablic od zera.
Implementacja w języku Java
Ponieważ Java nie posiada wbudowanego typu „krotka” (tuple), stworzyłem prostą klasę pomocniczą WynikMinMax, która elegancko przechowuje obie znalezione wartości.
Dlaczego to podejście jest lepsze?
W standardowym (naiwnym) podejściu każdy element porównujemy osobno z minimum i osobno z maksimum. Daje to łącznie 2n porównań.
W Twoim algorytmie:
Bierzemy parę elementów.
Porównujemy je ze sobą (1 porównanie).
Mniejszy porównujemy tylko z aktualnym min (1 porównanie).
Większy porównujemy tylko z aktualnym max (1 porównanie).
Razem zużywamy 3 porównania na każde 2 elementy. Matematycznie liczba porównań spada do około 23n, co czyni ten algorytm znacznie bardziej wydajnym przy bardzo dużych zbiorach danych.
Warto zauważyć: W kodzie Java użyłem pętli while zamiast for, aby łatwiej kontrolować „skoki” o dwa elementy oraz obsługę ostatniego, pojedynczego elementu w przypadku tablic o nieparzystej długości.
Napisz program, wyznaczy jednocześnie minimum i maksimum.
Specyfikacja problemu:
Dane:
ciag– ciąg liczb całkowitych zapisany w tablicy; tablica liczb całkowitych
Wynik:
min i max– najmniejszy i największy wyraz ciągu; liczba całkowita