[Teoria złożoności] Pesymistyczna, średnia złożoność czasowa

[111sadysta]

Rozpatrzmy następujący algorytm \(\displaystyle{ W}\) sprawdzający, czy element e występuje w tablicy \(\displaystyle{ A[0…n]}\)

Kod: Zaznacz cały

W(A[0…n],e)
1.	i <- 0
2.	A[n+1]  <> e
3.	while A[i]
4.	        do i <-  i+1
5.	if i<=n
6.	        then return TRUE
7.	        else 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ństo, tż. \(\displaystyle{ e=A \left[ i \right]}\) jest takie samo dla każdego \(\displaystyle{ i \in \{ 1 ... 100\}}\) .
Oblicz optymistyczną, pesymistyczną oraz średnią złożoność czasową tego algorytmu, mierząc liczbę porównań kluczy w wierszu 3.

[adek05]

Po pierwsze, to ajkoś dziwnie ten algorytm się prezentuje.
W while brak warunku, który może wyjaśni ideę wartownika(?) w linii poprzedniej.

Natomiast działa to najprawdopodobniej tak, że po prostu przebiegasz tablicę z lewa na prawo i szukasz danego e.
Stąd w przypadku pesymistycznym - e nie ma w tabeli - algorytm sprawdzi całą tablicę, stąd jego złożoność pesymistyczna: \(\displaystyle{ \mathcal{O} (n)}\) ze względu na n - długość tablicy.
W przypadku optymistycznym pierwszym elementem w tablicy będzie właśnie e - stąd złożoność \(\displaystyle{ \mathcal{O} (1)}\)

Teraz średnia...
Hmmm, nie znam prawdopodobieństwa na tyle by się tego podjąć
Na pewno z treści wynika, że dla \(\displaystyle{ \frac{3}{4}}\) danych aglorytm robi n porównań. Dla pozostałych \(\displaystyle{ \frac{1}{4}}\) przypadków prawdopodobieństwo, że element e znajdziemy po \(\displaystyle{ i}\) porównaniach wynosi: \(\displaystyle{ Pr_{i}=\frac{i}{n}}\). Może coś z tego wykminisz

[informatykmatematyk]

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.