W tym punkcie omówimy koszt średni algorytmu min_max2. Zauważmy najpierw, że dla ciągu rosnącego, algorytm w każdej iteracji będzie wykonywał tylko jedno porównanie, stale poprawiając wartość aktualnego maksimum. Dla ciągu malejącego natomiast, algorytm stale będzie wykonywał dwa porównania, gdyż to właśnie zmienna result.min, będzie za każdym razem modyfikowana. Naszym zadaniem jest ustalenie średniej liczby wykonanych porównań.

Niech D(n) oznacza zbiór wszystkich danych rozmiaru n w pewnej dowolnie ustalonej strukturze, P(d) prawdopodobieństwo wystąpienia danej dÎD(n) i t(d) koszt wykonania algorytmu min-max2 dla danych d, mierzony liczbą porównań. Wtedy koszt średni obliczymy ze wzoru:

Jak zwykle będziemy zakładali, że prawdopodobieństwo wystąpienia danych d jest takie samo dla wszystkich elementów d zbioru D(n).

Zauważmy, że zachowanie algorytmu min_max2 nie zależy ani od typu elementów ciągu, ani od ich konkretnej wartości. To co jest istotne, to relacje między elementami ciągu. Zamiast więc rozważać dowolne elementy, ograniczmy nasze rozważania do permutacji liczb naturalnych od 1 do n. Jak zwykle założymy, że wybranie konkretnych danych d, tzn. konkretnej permutacji, jest tak samo prawdopodobne, a więc, P(d) = 1/n!

Policzmy teraz oczekiwaną liczbę porównań wykonanych przez algorytm min_max2 dla dowolnie wybranej permutacji d. Pierwsze porównanie max £ e[i] wykonujemy przy każdej iteracji pętli. Natomiast test

wykonujemy tylko wtedy, gdy w pierwszym porównaniu odpowiedź była negatywna, czyli gdy na pozycjach 1,2...,i-1 były elementy większe od e[i]. Dla każdej permutacji d=(e[1],...,e[n]) wyznaczmy więc ciąg X[1],...,X[n] taki, że X[i] mówi, ile jest elementów większych od e[i] na pozycjach od 1 do i-1 w ciągu d.

Przykład 2.1
Jeżeli d jest ciągiem (3,4,6,2,1,5,7), to odpowiadający mu ciąg X-ów ma postać ( 0,0,0,3,4,1,0), bo na wcześniejszych pozycjach nie ma elementów mniejszych od 3, nie ma elementów mniejszych od 4, ale aż trzy elementy większe poprzedzają 2 i aż cztery elementy większe poprzedzają 1 itd. Zauważmy jeszcze, że pozycje zer w ciągu X odpowiadają wykonaniu tylko jednego porównania w algorytmie min_max2, a pozycje różne od zera odpowiadają wykonaniu przez nasz algorytm aż dwóch porównań.

S_2£i£n(1 + 1*P(X[i] ¹ 0)) = n-1 + S_2£i£n(1*(1-1/i)) = n-1 + n - S_1£i£n1/i .

Suma S_1£i£n1/i to n-ta liczba harmoniczna H_n. Grupując odpowiednio wyrazy sumy można wykazać (por. Invitation to Discrete Mathematics, J.Matoušek, J.Nešetřil) , że

Zatem ostatecznie, oczekiwaną liczbę porównań dla danych d możemy oszacować przez 2n-1 - ëlg nû/2 .

Twierdzenie 2.1

Średni koszt algorytmu min_max2 wyraża się wzorem A(n) = 2n-1 - ëlg nû/2 dla dowolnych danych rozmiaru n.

W następnych punktach tego wykładu poznamy algorytmy, które wykonują to samo zadanie z mniejszym, niż algorytm min_max2, kosztem.

Pytanie 2: Dla pewnej permutacji e liczb od 1 do 7 wyznaczono wektor X, w taki sposób, że X[i] jest liczbą elementów większych od e[i] na lewo od e[i] (tak jak w rozważaniach powyżej). Wiedząc, że wektor X=(0,0,2,2,1,0,3 ) wyznacz elementy ciągu e.