No i udało się zrobić całe 6A poprawnie, oto rozwiązanie:Obliczyć złożoność pesymistyczną i oczekiwaną algorytmu:
a) wyszukiwania liniowego (sekwencyjnego) elementu w nieposortowanym ciągu liczb
b) wyszukiwania binarnego w posortowanym ciągu liczb
pesymistyczna: \(\displaystyle{ W(n) = \max(t(I))}\)
oczekiwana: \(\displaystyle{ A(n) = \sum_{I = Dn}^{}p(I) \cdot t(I)}\)
\(\displaystyle{ W(n) = \max(i) = n}\)
\(\displaystyle{ A(n) = \sum_{i=1}^{n} \frac{1}{n} \cdot i = \frac{1}{n} \cdot \sum_{i=1}^{n} i =
\frac{1}{n} \cdot \frac{n(n+1)}{2} = \frac{n+1}{2}}\)
Wszystko ładnie, cacy. Problem pojawia się przy 6B:
pesymistyczna: \(\displaystyle{ W(n) = \lfloor \log_{2}n \rfloor + 1}\) (dobrze)
no i cały problem - oczekiwana:
Przykładowo dla \(\displaystyle{ A(n=7) = \frac{1}{7} \cdot 3 + \frac{1}{7} \cdot 2 + \frac{1}{7} \cdot 3 + \frac{1}{7} \cdot 1 + \frac{1}{7} \cdot 3 + \frac{1}{7} \cdot 2 + \frac{1}{7} \cdot 3 = \frac{1}{7} \cdot (1 \cdot 1 + 2 \cdot 2 + 4 \cdot 3)}\)
No i nie mam pomysłu jak z tym dalej ruszyć, końcowy wynika ma być następujący:
\(\displaystyle{ A(n) = \frac{1}{?} \cdot ((?+1)(?+1) + 1 - 2^{?+1} )}\)
Niestety mi totalnie inne rzeczy wychodzą, nie potrafię tego rozgryźć.