Algorytmy, o których mówiliśmy do tej pory działały "w miejscu", tzn. poza kilkoma zmiennymi pomocniczymi nie wykorzystywały żadnych dodatkowych struktur. Algorytm, który zamierzamy teraz omówić, używa dwóch dodatkowych tablic, o łącznej długości równej rozmiarowi danych.

Metoda

Porównujemy parami elementy ciągu. Element mniejszy z każdej pary zapamiętujemy w tablicy MNIEJSZE, a element większy z każdej pary zapamiętujemy w tablicy WIĘKSZE. Następnie w tablicy MNIEJSZE znajdujemy element minimalny, a w tablicy WIĘKSZE znajdujemy element maksymalny. Jeśli liczba elementów w ciągu nie jest parzysta, to element ostatni musi jeszcze być porównany ze znalezionym elementem minimalnym i, o ile nie jest od niego mniejszy, ze znalezionym elementem maksymalnym.

W przedstawionej realizacji tej metody użyjemy zmiennej result dla zapamiętania elementów najmniejszego i największego i dla uproszczenia założymy, że liczba elementów w ciągu e jest parzysta.

Poprawność algorytmu min_max4

Niezmiennikiem pętli w tym algorytmie jest formuła g postaci:

("j<k)($j₀<k) MNIEJSZE[j] £ WIĘKSZE[j₀] oraz ("j<k)($j₀<k) MNIEJSZE[j₀] £ WIĘKSZE[j].

Formuła ta mówi, że dla każdego elementu włożonego do tablicy MNIEJSZE znajdzie się element w tablicy WIEKSZE, który jest od niego większy, i odwrotnie. Ponadto, każdy element ciągu e, jest albo elementem tablicy MNIEJSZE, albo elementem tablicy WIĘKSZE. Jeśli szukamy elementu najmniejszego, to nie może się on znajdować w tablicy WIĘKSZE, bo zgodnie z formułą g po wykonaniu pętli, każdy element z tablicy WIĘKSZE ma od siebie mniejszy lub równy element w tablicy  MNIEJSZE. Podobnie, nie możemy szukać elementu największego wśród elementów MNIEJSZE, bo każdy element z tablicy MNIEJSZE ma od siebie większy lub równy element w tablicy WIĘKSZE. Wynika stąd, że element najmniejszy ciągu e znajduje się w tablicy MNIEJSZE, a element największy - w tablicy WIĘKSZE.

Z rozważań w poprzednim wykładzie wiemy, że funkcja minimum zastosowana do dowolnego niepustego ciągu zwraca element najmniejszy w tym ciągu. Na mocy założenia n ≥ 2, z czego wynika, że tablice MNIEJSZE i WIĘKSZE są niepuste. Zatem po wykonaniu  instrukcji {result.min := min(MNIEJSZE);} mamy

 result.min = MNIEJSZE[i] dla pewnego i = 1,..., n div 2,    result.min £ MNIEJSZE[k] dla  k=1,..., n div 2

oraz  po wykonaniu instrukcji {result.max := max(WIĘKSZE);} mamy

result.max = WIĘKSZE[i] dla pewnego i,      WIĘKSZE[k]  £ result.max dla  k=1,..., n div 2 .

Ostatecznie po wykonaniu programu, wartością zmiennej resunlt.min jest najmniejszy element ciągu e, a wartością zmiennej result.max jest największy element ciągu e.

Koszt algorytmu min_max4

Koszt tego algorytmu łatwo oszacować, bo w każdym kroku pętli wykonujemy (niezależnie od konkretnych wartości elementów ciągu)  dokładnie jedno porównanie, co łącznie daje n div 2 porównań. Z analizy algorytmów minimum i maksimum  wiemy (obie tablice pomocnicze mają długość [n/2]), że wykonują one dokładnie (n div 2 -1) porównań, co daje ostatecznie 3n/2 - 2 porównań,

T(min_max4,n) = 3n/2 - 2.

Przyglądając się bliżej podanej metodzie, dojdziemy z pewnością do wniosku, że tablice pomocnicze nie są nam potrzebne. Możemy przecież na bieżąco modyfikować zarówno wartość result.min jak wartość result.max, tak jak to się dzieje w algorytmach minimum i maksimum.

Idea tego nowego algorytmu będzie bardzo podobna do przedstawionej w min_max4. Rozważamy kolejne pary elementów. Z każdej pary wybieramy element mniejszy i porównujemy z aktualnie znalezionym elementem najmniejszym. Podobnie większy element z każdej pary porównujemy z aktualnie znalezionym elementem największym. Po przejrzeniu wszystkich par znajdziemy równocześnie element najmniejszy i element największy. Podobnie jak w poprzednim algorytmie, założymy dla wygody, że liczba elementów w ciągu e jest parzysta i większa od 1.

Poprawność algorytmu min_max5

Niezmiennikiem w tym algorytmie (porównaj komentarze) jest formuła

("j £ i-1) (result.min £ e[j] £ result.max).

Rzeczywiście, jeśli przy pewnej wartości i wchodzimy do pętli i spełniona jest formuła ("j £ i-1) (result.min £ e[j] £ result.max), która mówi, że wartością result.min jest element najmniejszy, a wartością result.max jest element największy ze wszystkich  elementów o indeksach mniejszych niż i, to porównując result.min z mniejszym elementem następnej pary (e[i],e[i+1]), a result.max z większym elementem tej pary, znajdziemy element najmniejszy ze wszystkich elementów aż do (i+1)-go. Podobnie porównując result.max z większym elementem tej pary, znajdziemy element największy ze wszystkich elementów aż do (i+1)-go. Ponieważ przed wejściem do pętli niezmiennik jest prawdziwy, to po wyjściu z pętli jest również prawdziwy. Ponadto, po wyjściu z pętli wartością zmiennej i jest n+1. Dowodzi to poprawności algorytmu min_max5 ze względu na warunek początkowy (n>1 Ù n mod 2 = 0) i warunek końcowy ("j £ n) (result.min £ e[j] £ result.max).

Koszt algorytmu min_max5

Koszt algorytmu min_max5, tak jak wszystkich poprzednich, mierzymy liczbą wykonanych porównań elementów danego ciągu. Przyjmijmy n=2k. Przed wejściem do pętli wykonujemy 1 porównanie. W pętli wartości zmiennej i, kontrolującej pętlę, zmieniają się co 2. Zatem pętla wykona (n-2)/2 iteracji. W każdej iteracji wykonujemy 3 porównania, co daje łączny koszt

T(min_max5) = 3 (n-2)/2 +1 = 3n/2-2.

Koszt tego algorytmu jest więc taki sam, jak koszt dwóch poprzednich algorytmów. Nie wykorzystuje on rekursji i nie korzysta z dodatkowych miejsc pamięci, poza trzema zmiennymi pomocniczymi. Ponadto algorytm ten nie modyfikuje stanu ciągu wejściowego, co czasami jest istotne dla dalszej obróbki tych danych.

Na zakończenie tego punktu zanotujmy jeszcze, że omawiany algorytm jest optymalny w klasie algorytmów rozwiązujących problem min-max w modelu drzew decyzyjnych, tzn. przez porównywanie elementów. Oznacza to, że każdy algorytm tej klasy dla danych rozmiaru  n musi w przypadku pesymistycznym wykonać co najmniej 3n/2 -2 porównań.

Dowód optymalności pomijamy. Dociekliwych Czytelników odsyłamy do książki Elementy analizy algorytmów, L. Banachowski, A. Kreczmar, WNT, 1982.

Pytanie 5: Jaki jest koszt pamięciowy algorytmu min_max4?