Często w analizie danych spotykamy się z problemem znalezienia najmniejszego i największego elementu w zbiorze. Na pierwszy rzut oka wydaje się to proste, ale można podejść do tego problemu na różne sposoby. Dwa popularne podejścia to metoda naiwna i metoda optymalna, które opiszę w tym artykule. Pokażę pseudokod, implementacje w C++ i Pythonie, a także omówię ich efektywność.

Algorytm naiwny

Podejście naiwne polega na iteracji przez zbiór dwa razy, najpierw, aby znaleźć najmniejszy element, a następnie, aby znaleźć największy element. Zobaczmy, jak to wygląda w pseudokodzie:

Jest to proste i intuicyjne rozwiązanie, ale nie jest optymalne. Jego złożoność obliczeniowa wynosi O(2n), ponieważ musimy przejść przez cały zbiór dwa razy.

Teraz zobaczmy, jak ten algorytm wygląda w C++ i Pythonie.

C++:

Szczegółowy opis powyższego algorytmu można zawrzeć w następujących krokach:

1. #include <vector> #include <utility> - Te linie dodają do programu odpowiednie biblioteki. vector jest potrzebny do obsługi wektorów (dynamicznych tablic), a utility pozwala nam używać klas takich jak pair, który używamy do zwracania dwóch wartości z funkcji.

2. std::pair<int, int> znajdzMinMaxNaiwnie(const std::vector<int>& zbior) - Tutaj deklarujemy naszą funkcję. Zwraca ona parę liczb całkowitych (nasze min i max), a jako argument przyjmuje wektor liczb całkowitych.

3. int najmniejszy = zbior[0]; int najwiekszy = zbior[0]; - Na początku funkcji inicjalizujemy dwie zmienne: najmniejszy i najwiekszy, przypisując im wartość pierwszego elementu w wektorze. Zakładamy, że wektor nie jest pusty.

4. for (int element : zbior) - Ten kod rozpoczyna pętlę for, która przechodzi przez każdy element wektora. W każdej iteracji element przyjmuje wartość kolejnego elementu z wektora.

5. if (element < najmniejszy) - Ta instrukcja warunkowa sprawdza, czy bieżący element jest mniejszy od aktualnie najmniejszego elementu.

6. najmniejszy = element; - Jeśli warunek powyżej jest spełniony, bieżący element staje się nowym najmniejszym elementem.

7. Podobne kroki powtarzamy dla największego elementu. Przechodzimy przez wektor ponownie i sprawdzamy, czy bieżący element jest większy od aktualnie największego elementu. Jeżeli tak, to aktualizujemy nasz największy element.

8. return {najmniejszy, najwiekszy}; - Na końcu funkcji zwracamy parę najmniejszego i największego elementu.

Python:

Algorytm optymalny

Optymalny algorytm polega na jednoczesnym znalezieniu najmniejszego i największego elementu podczas jednej iteracji. W ten sposób złożoność obliczeniowa wynosi O(n), co jest o połowę szybsze od algorytmu naiwnego. Poniżej przedstawiam pseudokod algorytmu optymalnego:

W tym podejściu, dla każdego elementu w zbiorze, sprawdzamy, czy jest on mniejszy lub większy od aktualnego najmniejszego lub największego elementu. Jeżeli tak, to aktualizujemy odpowiednio najmniejszy lub największy element.

Teraz zobaczmy, jak ten algorytm wygląda w C++ i Pythonie.

C++:

Python:

Jak widać, algorytm optymalny jest nie tylko wydajniejszy, ale także nieznacznie prostszy do zrozumienia i implementacji niż algorytm naiwny. Pamiętaj jednak, że różnica w wydajności między tymi dwoma algorytmami stanie się zauważalna dopiero dla dużych zbiorów danych. Dla małych zbiorów oba algorytmy powinny działać równie dobrze.