Znajdowanie najmniejszego i największego elementu

kategoria: Zadania z programowania

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.

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.

wyszukiwanie-elementow1

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.

wyszukiwanie-elementow2

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:

  1. sprawdzenie czy \(A>B\)
  2. sprawdzenie czy \(A>max\) (lub \(B>max\))
  3. 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.