W dniu 10.10.2010 00:03, Mariusz Marszałkowski pisze:
> Prawdopodobieństwo złożoności N * LOG( N ) :
[...]
> To się nie zdarzy nigdy :)
Tak samo jak przypadek w pełni optymistyczny :)

Komentarz statystyczny:
Tu mamy dyskretną dziedzinę, więc prawdopodobieństwo w punkcie jest !=0
(i wynosi jeżeli się nie pomyliłem z racji pory (1/k)^(n-1)) ale dla
rozkładu ciągłego prawdopodobieństwo w punkcie JEST równe zero. Dlatego
operuje się całkami. Bo czy przypadek w którym wszystkie poza jednym
trafiły do tego samego kubełka nie jest "z praktycznego punktu widzenia"
równie pesymistyczny jak przypadek "w pełni pesymistyczny"?

No i wtedy możemy konstruować twierdzenia na zasadzie:
z prawdopodobieństwem Ó ilość wykonanych operacji będzie:
- większa od Ą
- mniejsza od Ą
- zawarta w przedziale <Ą,Ę>


>
> Może ktoś policzy do końca?
Message-ID: <i8qnsn$21h$1@news.onet.pl>
Policzyłem przypadek optymistyczny ;) - liczy się go znacznie prościej
bo z założeniem równomiernego rozkładu, a lepiej się i tak nie da.

--
Pozdrawiam
Michoo