I_R_W14_M25_Java Szukanie jednoczesne min‑max
Algorytm jednoczesnego znajdowania minimum i maksimum
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), stworzyliśmy 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 2/3n, co czyni ten algorytm znacznie bardziej wydajnym przy bardzo dużych zbiorach danych.
Warto zauważyć
W kodzie Java użyliśmy 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, który 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