On 11 Maj, 07:41, Maciej Pilichowski
<P...@g...com> wrote:
> On Mon, 10 May 2010 11:52:38 -0700 (PDT), Mariusz Marszałkowski
>
> <m...@g...com> wrote:
> >To ile wykonuje porównań je?li nie n * log(n) ?
>
> Zwykly quicksort
Rozmawiamy o zrandomizowanym quicksorcie.

> jest solidnie opisany w Cormenie.
Cormen podaje właśnie n*log(n)

> W skrocie: to zalezy od danych i wyboru elementu osiowego.
Prawdopodobieństwo istotnego(!) zwiększenia ilosci porownan z
powodu pechowego wyboru elementów osiowych, czyli np. zwiększenia
z n*log(n) do n^2 maleje ze wzrostem liczby sortowanych
elementów przybliżeniu jak 1/n!. Dla dużych N mozna pominac, dla
malych qsorta sie nie stosuje z powodu duzego narzutu liniowego.

W pierwszym poście oczywiście się pomylilem, należy mianownik
zamienić z licznikiem. Oszacowanie prawdopodobienstwa ze para zostanie
porównana wynosi:
ilosc_porownan / ilosc_par => n*log(n) / n*(n-1) => log(n) / (n-1)

Pozdrawiam