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.

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 minmax 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 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ść 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.

Dane posortowane

Warto wspomnieć jeszcze o przypadku specjalnym, kiedy otrzymane dane są posortowane. Wtedy wystarczy wziąć elementy brzegowe, które będą odpowiadać wartościom największej oraz najmniejszej.

Wtedy złożoność czasowa wynosi O(1), a więc jest stała – niezależna od wielkości danych wejściowych.

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *