On 29.09.2014 13:47, Wojciech Muła wrote:
> Witajcie, w normalnym wyszukiwaniu binarnym element "środkowy" (c)
> jest średnią arytmetyczną indeksów pierwszego (a) i ostatniego (b)
> z przetwarzanego przedziału.
>
> A teraz weźmy c := liczba losowa z przedziału [a, b] (np. z rozkładem
> normalnym).

Na pewno normalnym? To z jaką wariancją. Jak radzić sobie z wyjściem
poza [a,b] (rozkłąd normlany o dowolnej średniej i std jest -inf..inf),
co najwyżej odpowiednio doże liczby są w praktyce niemożliwe do
wylosowania.

Może miałeś na myśli rozkład jednostajny?

> Czy znacie jakieś artykuły, które by takie wyszukiwanie
> analizowały? Jeśli dobrze pamiętam w Cormenie było porównanie
> wyszukiwania liniowego z losowym.

W cormenie na pewno przy wyszukiwaniu binarnym było wyszukiwanie
interpolacyjne, natomiast losowy wybór elementu dzielącego
był w wersji qsort.
Czy gdzieś (np w ćwiczeniach) była wersja wyszukiwania z losowaniem,
nie wiem, możesz podać dokładniejsze namiary?

Zwykły binsearch ma czas (liczba porównań w zależności
od dlugości tablicy)
T[L] = 0 dla L<=1
T[L] = 1+T(L/2) L>1. [ok, z grubsza;)]

Stąd T[L] = log_2 (L)


W przypadku losowania z rozkładu jednostajnego będzie to coś w rodzaju
T[L] = 1+sum(i=1,L-1) ro(i,L)(T[i] (i)*L + T[L-i]*(L-i)/L) [1]
{zakładam, że w wyniku podziału nie moze powstać pusta tablica}

{ średnia po wynikach losowania, wynikiem losowania jest
i, na i/L szukany obiekt jest w tablicy dlugosci i, na 1 - i/L w
pozostałej części. ro(i,L) to gęstość rozkładu}

Dla ro(i,L) z rozkładu jednostajnego mamy = 1/(L-1)

Szybki wykres:
[matlab]
N=2000;

Tb=zeros(N,1);
for L=2:N,
j=floor(L/2);
Tb(L) = 1+ j/L *Tb(j) + (L-j)/L* Tb(L-j);
% Tb(L) = 1+ mean( ((j).* Tb(j) +(L-j).* Tb(L-j))/(L) ); %
rownoważnie
end

T=zeros(N,1);

for L=2:N,
%j=floor(L/2);
j=(1:L-1)'; %podziały
T(L) = 1+ mean( ((j).* T(j) +(L-j).* T(L-j))/(L) );
end

plot(1:N,Tb,'o',1:N,T,'*',1:N,log2(1:N))

Wersja randomizowana jest też logarytmiczna, ale ciut wolniejsza
(jeśli chodzi o liczbę porównań, to tego dojdzie generowani liczb
losowych)
https://www.dropbox.com/s/e58tjr9ke5t1izl/randbinsea
rch.png?dl=0
Niebieski to zwyczajny bsearch. Czerwona cienka linia to log2.

Po policzeniu nie ma w tym nc zaskakującego;) Wzór [1] na T[L]
to jakaśtam średnia z fukcji
x T(x) + (L-x) T(L-x). [2]

Ma ona symetrie względem L/s, czyli tam jest ekstermum.
Spodziewamy się [pd T(x) funkcji wyglądającej jak logarytm).
x log(x) + (L-x)log(L-x) ma w L/2 minimum.
Lepiej więc wziąć po prostu L/2, niż średnią (a to, dla wartości
oczekiwanej, robimy randomizując punkt podziału).


A, do rzeczy. Skoro algorytm jest wyraźnie gorszy, wątpię, by
ktoś o nim coś więcej i dokładniej pisał. Ale mogę czegoś nie
zauważać.

pzdr
bartekltg