Znajdowanie najmniejszego i największego elementu
Znajdywanie najmniejszego i największego elementu tablicy jest pozornie prostym zadaniem, ale tylko w przypadku, jeżeli zadanie nie zostanie dodatkowo skomplikowane. Jeżeli zastosujemy pewne specjalne podejście, wtedy algorytm może działać szybciej.
Spis treści
Algorytm naiwny
Algorytm naiwny jest najprostszą metodą na znalezienie największego i najmniejszego elementu. Polega on na sprawdzeniu każdej liczby w tablicy i zapisywaniu wartości najmniejszych i największych.
Taki algorytm ma złożoność czasową \(O(n)\), ponieważ czas jego wykonania zależy wprost proporcjonalnie od liczby elementów tablicy. Dla każdego obiegu pętli wykonuje \(2n\) porównań.
#include <cstdlib>
#include <iostream>
using namespace std;
int main()
{
int liczby[10] = {6,1,2,5,7,3,8,9,4,5};
int min = 9999;
int max = -1;
for (int i = 0; i<10; i++)
{
if (liczby[i] < min)
{
min = liczby[i];
}
if (liczby[i] > max)
{
max = liczby[i];
}
}
cout << "Liczba min to: " << min << endl;
cout << "Liczba max to: " << max << endl;
system("PAUSE >NUL");
return 0;
}
W powyższym algorytmie zmienne min oraz max są ustawione na jakieś losowe duże i małe liczby. Możemy zmniejszyć ilość porównań ustawiając domyślne wartości zmiennych min i max na pierwszy element tablicy. Dzięki temu iterowanie po tablicy możemy rozpocząć z pominięciem pierwszego elementu. Ilość porównań spada dzięki temu do \(2n-2\).
#include <cstdlib>
#include <iostream>
using namespace std;
int main()
{
int liczby[10] = {6,1,2,5,7,3,8,9,4,5};
int min = liczby[0];
int max = liczby[0];
for (int i = 1; i<10; i++)
{
if (liczby[i] < min)
{
min = liczby[i];
}
if (liczby[i] > max)
{
max = liczby[i];
}
}
cout << "Liczba min to: " << min << endl;
cout << "Liczba max to: " << max << endl;
system("PAUSE >NUL");
return 0;
}
Algorytm optymalny
W podstawie programowej matury z informatyki jest wzmianka, że obowiązuje Cię zarówno znajomość metody naiwnej oraz optymalnej. Algorytm optymalny polega na przeszukiwaniu zbioru dwójkami, a nie element po elemencie. Dzięki temu ilość porównań jest mniejsza.
Przy każdym obrocie pętli wczytujemy dwie kolejne liczby A i B. Następnie sprawdzamy, która z nich jest większa.
- jeżeli większa jest liczba A wtedy nie bierzemy jej pod uwagę jako potencjalnie najmniejszej, tym samym skoro B jest mniejsza to nie bierzemy jej pod uwagę jako potencjalnie największej
- jeżeli większa jest liczba B wtedy nie bierzemy jej pod uwagę jako potencjalnie najmniejszej, tym samym skoro A jest mniejsza to nie bierzemy jej pod uwagę jako potencjalnie największej
Na końcu należy sprawdzić jeszcze ostatni element w wypadku, gdyby ilość elementów tablicy była nieparzysta. Złożoność czasowa algorytmu nadal wynosi \(O(n)\), a więc jest liniowo zależna od liczby elementów tablicy, jednak liczba porównań wynosi \(\frac{3n}{2}\).
#include <cstdlib>
#include <iostream>
using namespace std;
int main()
{
int n = 10;
int liczby[n] = {6,1,2,5,7,3,8,9,4,5};
int min = 99999;
int max = -1;
for (int i = 0; i < n - 1; i += 2)
{
// jezeli A jest wieksze od B
if (liczby[i] > liczby[i+1])
{
if (liczby[i] > max)
{
max = liczby[i];
}
if (liczby[i+1] < min)
{
min = liczby[i+1];
}
}
// jezeli B jest wieksze od A
else
{
if (liczby[i+1] > max)
{
max = liczby[i+1];
}
if (liczby[i] < min)
{
min = liczby[i];
}
}
}
// ilosc nieparzysta, sprawdzamy ostatni element
if (n % 2 == 1)
{
if (liczby[n-1] > max)
{
max = liczby[n-1];
}
if (liczby[n-1] < min)
{
min = liczby[n-1];
}
}
cout << "Liczba min to: " << min << endl;
cout << "Liczba max to: " << max << endl;
system("PAUSE >NUL");
return 0;
}
Skąd wzięła się złożoność \(\frac{3n}{2}\)? Dla każdego obiegu pętli wykonujemy 3 porównania:
- sprawdzenie czy \(A>B\)
- sprawdzenie czy \(A>max\) (lub \(B>max\))
- sprawdzenie czy \(B<min\) (lub \(A<min\))
Ilość liczb jest jednak o połowę mniejsza, ponieważ iterujemy dane dwójkami a nie liczba po liczbie.
