I_R_W14_M25_C++ Szukanie jednoczesne min‑max
Algorytm równoczesnego wyszukiwania w zbiorze największej i najmniejszej wartości (metoda iteracyjna).
W wielu zadaniach algorytmicznych zachodzi potrzeba znalezienia najmniejszego (minimum) oraz największego (maksimum) elementu w zbiorze danych, na przykład w tablicy liczb. Najprostszym rozwiązaniem tego problemu jest wykonanie dwóch osobnych przeglądów danych – jednego w celu znalezienia minimum, a drugiego w celu znalezienia maksimum. Podejście to jest poprawne, lecz nieefektywne, ponieważ wymaga dużej liczby porównań.
Algorytm jednoczesnego wyszukiwania minimum i maksimum umożliwia znalezienie obu wartości w jednym przeglądnięciu danych. Jego istotą jest odpowiednia organizacja porównań, najczęściej poprzez porównywanie elementów parami, co pozwala ograniczyć ich liczbę i zwiększyć efektywność obliczeń.
W bardziej efektywnej wersji iteracyjnej elementy są porównywane parami. Najpierw porównuje się dwa sąsiednie elementy, aby ustalić, który z nich jest mniejszy, a który większy. Następnie mniejszy z pary porównywany jest tylko z aktualnym minimum, a większy tylko z aktualnym maksimum. Takie podejście pozwala zmniejszyć liczbę porównań i zwiększyć wydajność algorytmu.
Warto zauważyć, że algorytm ten można zapisać zarówno w formie iteracyjnej, wykorzystującej pętle, jak i w formie rekurencyjnej, opartej na dzieleniu problemu na mniejsze podproblemy i łączeniu uzyskanych wyników. Dzięki temu algorytm stanowi dobry przykład ilustrujący różne podejścia do rozwiązywania tego samego problemu algorytmicznego.
Metoda iteracyjna jest łatwa do implementacji, wydajna czasowo i nie wymaga dodatkowej pamięci, dlatego jest najczęściej stosowanym sposobem realizacji algorytmu jednoczesnego wyszukiwania minimum i maksimum w praktycznych programach.
Słownik
(z łac. iteratio) powtarzanie w pętli tych samych instrukcji aż do spełnienia pewnego warunku
metoda polegająca na podzieleniu problemu na mniejsze, prostsze do rozwiązania podproblemy; po całkowitym rozbiciu problemu oraz rozwiązaniu podproblemów, łączymy je z powrotem w całość i rozwiązujemy cały problem
technika programowania polegająca na odwoływaniu się procedur lub funkcji do samych siebie, aż do momentu spełnienia warunku podstawowego
najprostsze, bezpośrednie rozwiązanie danego problemu, pozbawione jakichkolwiek usprawnień i optymalizacji, przez co zazwyczaj jest to rozwiązanie nieoptymalne; przykładami mogą być algorytmy, które sprawdzają wszystkie możliwe rozwiązania (podczas gdy wystarczyłoby sprawdzenie tylko części), przeszukują całe zbiory danych (podczas gdy wystarczyłoby tylko częściowe przeszukiwanie) itp.
czas niezbędny do rozwiązania określonego problemu, podawany zazwyczaj w liczbach operacji dominujących; złożoność czasowa zależy od ilości danych wejściowych