Witam, odświeżam wątek ponieważ mam to samo zadanie:
Rozpatrzmy następujący algorytm W sprawdzający, czy dany element e znajduje się w tablicy A[1...n] :
Kod: Zaznacz cały
W(A[1...n],e)
1. i = 1
2. while i <= n
3. do if A[i] = e
4. then return TRUE
5. i = i + 1
6. return FALSE
Niech
\(\displaystyle{ n=100}\). Zakładamy, że prawdopodobieństwo, tż.
\(\displaystyle{ e \in A \left[ 0 ... 100 \right]}\)wynosi
\(\displaystyle{ \frac{1}{4}}\) oraz prawdopodobieństwo, tż.
\(\displaystyle{ e=A \left[ i \right]}\)jest
takie samo dla każdego i
\(\displaystyle{ \in \{ 1 ... 100\}}\) .
a) Oblicz optymistyczną, pesymistyczna i średnią złożoność czasową tego algorytmu mierzoną liczbą porównań kluczy w wierszu 3.
b) Oblicz optymistyczną, pesymistyczna i średnią złożoność czasową tego algorytmu mierzoną liczbą wszystkich porównań (wiersz 2 i 3).
Optymistyczną i pesymistyczną ogarnąłem, ale nie rozumie jak mam się zabrać za średnią prosił bym o pomoc. Z góry dziękuje.