Problem, który rozważymy w tym punkcie, to znalezienie elementu najmniejszego i największego w danym skończonym zbiorze, reprezentowanym przez tablicę e o elementach e[1], ..., e[n]. Dla uproszczenia nazywać będziemy ten problem min-max. Zaczniemy od prostego rozwiązania, tzw. algorytmu naiwnego, który w następnych punktach tego wykładu nieco poprawimy. Przyjmiemy, że poszukiwany algorytm będzie używał zmiennej result, reprezentującej obiekt o dwóch atrybutach : min i max, na których zostaną zapamiętane wyniki.

Algorytm rozwiązujący problem  min-max, interpretowany w strukturze, w której uniwersum jest zbiorem liniowo uporządkowanym,  powinien być poprawny ze względu na następującą specyfikację:

 wp = {n>0},  

wk = {($ i₀,i₁ £ n) (e[i₀]=result.min Ù e[i₁] = result.max), ("j£ n)(e[i] £ result.min Ù result.max £ e[i])}.

Metoda

Najprostszym rozwiązaniem problemu min-max jest znalezienie najpierw elementu największego, a potem elementu najmniejszego przez dwukrotne przeglądanie ciągu. Jeżeli kolejny element jest większy od największego znalezionego do tej pory, to będzie on teraz elementem największym. Podobnie przy wyszukiwaniu elementu najmniejszego: porównujemy kolejne elementy ciągu ze znalezionym elementem najmniejszym i ewentualnie poprawiamy jego wartość, tak by wartością zmiennej result.min był element najmniejszy ze wszystkich przejrzanych do tej pory elementów.  Algorytm może być zapisany następująco:

Pełną analizę poprawności tego algorytmu pozostawiamy Czytelnikowi (por. wykład 01). Stwierdzimy teraz tylko, że niezależnie od typu elementów ciągu, jeżeli tylko relacja £ jest liniowym porządkiem, to po wykonaniu algorytmu prawdziwa będzie formuła 

 (" i£ n) (e[i] £ result.max Ù result.min £ e[i]).

Co więcej, wartościami zmiennych  result.min i result.max są elementy rozważanego ciągu. Zatem

Zauważmy, że liczba wykonywanych operacji nie zależy od kolejności elementów w ciągu. Przyjmując n jako rozmiar danych i porównywanie jako operację dominującą, z łatwością oszacujemy czasowy koszt algorytmu min_max1: T(n) = 2n - 2.

Ten prosty algorytm nie jest jednak najlepszy. Po pierwsze, zamiast dwukrotnie przeglądać wszystkie elementy, raz w poszukiwaniu elementu największego i drugi raz w poszukiwaniu elementu najmniejszego, można wykonać tylko jedną  pętlę.

Taki zabieg uprościł nieco strukturę algorytmu, ale nadal wykonujemy 2(n-1) porównań. Teraz jednak łatwo zauważymy, że jeśli jakiś element e[i] jest większy od aktualnego maksimum, to przecież ten element nie może być jednocześnie elementem mniejszym od aktualnego minimum i nie musimy wykonywać drugiego porównania. Zatem algorytm może przyjąć postać:

Teraz jednak łatwo zauważyć, że koszt algorytmu zależy od tego, jakie są wzajemne zależności między elementami ciągu, czyli zależy od kolejności w jakiej zapisane są elementy w ciągu. W najgorszym razie algorytm wykona 2n-2 porównania. Stanie się tak np. dla dowolnego ciągu uporządkowanego malejąco. Dyskusję kosztu średniego algorytmu przedstawimy w następnym punkcie tego wykładu. Teraz zajmiemy się przeanalizowaniem jego poprawności.

Załóżmy, że wykonujemy algorytm min-max2 w strukturze danych STR, w której określona jest relacja porządku liniowego £, a elementy tablicy e[1:n] należą do uniwersum tej struktury. Po wykonaniu pierwszych trzech instrukcji przypisania, oba atrybuty zmiennej result  są równe e[1], a i=2. Zatem  prawdziwa jest własność

("j< i)(e[j] £ result.max Ù result.min £ e[j]).

Załóżmy teraz, że po pewnej liczbie iteracji pętli "while" spełniona jest formuła g(i) postaci  result.min £ e[j], e[j] £ result.max dla j=1,...,(i-1). Prześledźmy co się stanie w następnej iteracji. Jeżeli rozważany element e[i] jest większy od wartości zmiennej max, to, po wykonaniu przypisania result.max := e[i], wartością zmiennej result.max jest największy spotkany do tej pory element. Jeżeli natomiast element e[i] nie jest większy od result.max, to  stara wartość zmiennej max wskazuje element największy.  Wykonane instrukcje nie zmieniły wartości zmiennej result.min, zatem po wykonaniu pierwszego porównania mamy

e[j] £ result.max dla j=1,...,(i-1),i,  oraz result.min £ e[j] dla j=1,...,(i-1).

Drugie porównanie (to po "else") wykonujemy tylko wtedy, gdy rozważany element e[i] był niewiększy od aktualnego maksimum. Jeśli e[i] jest mniejsze od wartości aktualnego minimum, wykonujemy instrukcję przypisania result.min := e[i]. Oczywiście, ani sprawdzenie testu w "if", ani wykonanie tej instrukcji przypisania, nie zmieniają wartości result.max. Po wykonaniu pierwszej instrukcji pętli spełniona jest zatem własność  g(i+1) postaci

e[j] £ result.max dla j=1,...,(i-1),i oraz result.min £ e[j] dla j=1,...,(i-1),i.

Wewnątrz pętli pozostała do wykonania instrukcja przypisania i := i+1; Mamy zatem starą wartość zmiennej i zastąpić wartością większą o 1. Zastępując w formule g(i+1), wyrażenie (i+1) przez i, otrzymujemy  formułę  g(i):

result.min £ e[j],        e[j] £ result.max dla j=1,...,(i-1).

Udowodniliśmy więc, że jeśli na początku kolejnej iteracji g(i) jest spełnione, to jest też spełnione po wykonaniu tej iteracji. Formuła g(i) jest niezmiennikiem pętli w tym algorytmie. Zatem po wyjściu z pętli, co jest możliwe dopiero wtedy, gdy i= n+1, również spełniona jest formuła  g(i). Na wyjściu prawdziwa jest więc formuła postaci:

(result.min £e[1] £ result.max) Ù  (result.min £ e[2] £ result.max ) Ù ... Ù (result.min £e[i-1] £ result.max ) Ù (i = n+1),

a ponieważ wartościami zmiennych result.min, result.max są elementy danego ciągu, to prawdziwy jest warunek końcowy przyjętej specyfikacji algorytmu.

Jest oczywiste, że algorytm min_max2 zatrzymuje się dokładnie po n-1 iteracjach, ponieważ n jest liczbą naturalną, a wartościami zmiennej i, kontrolującej pętlę, są kolejne liczby naturalne zaczynając od 2. Ostatecznie

Pytanie 2: Czy algorytm min_max2 działa poprawnie i jaki będzie wynik algorytmu, jeśli n=0? 

Zobacz odpowiedź