On Tuesday, September 30, 2014 7:20:23 AM UTC+2, Wojciech Muła wrote:
> Właśnie miałem nadzieję, że ktoś zauważył - np., że dla jakiegoś szczególnego
> rozkładu danych wejściowych wersja randomizowana sprawdza się lepiej.
Co znaczy lepiej?

Generalnie musimy znalezc pozycje elementu w tablicy.
Kazda metoda wyszukiwania charakteryzuje sie prawdopodobienstwem p(i) ze
zakonczy dzialanie w i-tej iteracji, albo p(t), ze zakonczy dzialnie w
czasie t. Mamy funkcję kosztu k(t), ktora to funkcja opisuje koszt wyszukania w
czasie t. Mozemy minimalizowac esperancje: suma od 0 do inf p(t)*k(t).

Jesli znasz k(t) i jesli wiesz cos o danych, to mozesz analizowac i/albo
testowac rozne metody wyszukiwania. Np. ksiazki telefonicznej nie trzeba
otwierac w sordku.

Pozdrawiam