On Tuesday, September 30, 2014 12:22:33 AM UTC+2, bartekltg wrote:
> 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?

Tak, jednostajny. Pomyłka (i to nie imię mojej żony :) ).

> 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?

Moja kopia Cormena leży 450 km stąd, dlatego zapytałem.

> [...]

Wielkie dzięki.

> Wersja randomizowana jest też logarytmiczna, ale ciut wolniejsza
> (jeśli chodzi o liczbę porównań, to tego dojdzie generowani liczb
> losowych)
> [...]
> 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ć.

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.

w.