Jeśli mamy ciąg \(\displaystyle{ n}\) liczb i stosujemy algorytm liniowego wyszukiwania zadanej wartości \(\displaystyle{ x}\) w tym ciągu, a w tym ciągu ta wartość pojawia się \(\displaystyle{ k}\) razy, to wartość oczekiwana liczby porównań wynosi \(\displaystyle{ \frac{n+1}{k+1}}\), gdzie \(\displaystyle{ 1 \le k \le n}\).
Dlaczego akurat tyle?
Proszę o wytłumaczenie.
Wartość oczekiwana liczby porównań.
-
bartek118
- Użytkownik
- Posty: 5974
- Rejestracja: 28 lut 2010, o 19:45
- Płeć: Mężczyzna
- Lokalizacja: Toruń
- Podziękował: 15 razy
- Pomógł: 1251 razy
Re: Wartość oczekiwana liczby porównań.
Popatrzmy dla prostoty na przypadek \(\displaystyle{ k=1}\) pozostawiając Tobie próbę obliczenia dla \(\displaystyle{ k > 1}\). Niech \(\displaystyle{ X}\) oznacza liczbę porównań, poszukujemy \(\displaystyle{ \mathbb{E} X}\). Zmienna \(\displaystyle{ X}\) przyjmuje wartości w zbiorze \(\displaystyle{ \{1,2,\ldots, n\}}\). Przypomnijmy, że
\(\displaystyle{ \mathbb{E} X = \sum_{j=1}^n j \cdot \mathbb{P}(X=j).}\)
Obliczmy \(\displaystyle{ \mathbb{P}(X=j)}\). Algorytm wykona dokładnie \(\displaystyle{ j}\) kroków, jeśli szukany element znajduje się na pozycji \(\displaystyle{ j}\). Szansa na to wynosi dokładnie \(\displaystyle{ \frac{1}{n}}\). Stąd
\(\displaystyle{ \mathbb{E} X = \sum_{j=1}^n j \cdot \frac{1}{n} = \frac{1}{n} \sum_{j=1}^n j = \frac{1}{n} \cdot \frac{n(n+1)}{2} = \frac{n+1}{2} = \frac{n+1}{k+1}, \quad \mathrm{gdzie} \ k=1.}\)
Spróbuj powtórzyć to dla dowolnego \(\displaystyle{ k}\) - różnica będzie jedynie w obliczeniu \(\displaystyle{ \mathbb{P}(X=j)}\).
\(\displaystyle{ \mathbb{E} X = \sum_{j=1}^n j \cdot \mathbb{P}(X=j).}\)
Obliczmy \(\displaystyle{ \mathbb{P}(X=j)}\). Algorytm wykona dokładnie \(\displaystyle{ j}\) kroków, jeśli szukany element znajduje się na pozycji \(\displaystyle{ j}\). Szansa na to wynosi dokładnie \(\displaystyle{ \frac{1}{n}}\). Stąd
\(\displaystyle{ \mathbb{E} X = \sum_{j=1}^n j \cdot \frac{1}{n} = \frac{1}{n} \sum_{j=1}^n j = \frac{1}{n} \cdot \frac{n(n+1)}{2} = \frac{n+1}{2} = \frac{n+1}{k+1}, \quad \mathrm{gdzie} \ k=1.}\)
Spróbuj powtórzyć to dla dowolnego \(\displaystyle{ k}\) - różnica będzie jedynie w obliczeniu \(\displaystyle{ \mathbb{P}(X=j)}\).