On 9 Paź, 23:41, bartekltg <b...@g...com> wrote:
> On 9 Paź, 22:41, Mariusz Marszałkowski <m...@g...com> wrote:
>
> > Ale w jaki problem? Na moje w ten sposób sprawa się upraszcza.
> > Najlepiej jakby wylosowało się 10^6 takich samych liczb.
>
> Problem jest taki, że jeśli dane musimy pamietać (a nie np zliczać
> krotność wystąpień danej liczby) to i tak mamy nlogn.
> Michoo własnie o tym pisał.

Z reguły takich samych danych nie musimy pamiętać, często
można zapamiętać jedną i ich ilość. Tutaj, jeśli dobrze rozumiem
problem, wystarczy liczyć od zera do dwóch.
0 - brak liczby
1 - jedna liczba
2 - dwie lub więcej
W przypadku gdy przechodzimy ze stanu 1 do 2, zapamiętujemy
liczbę na stosie. Pod koniec algorytm wyświetla wszystkie
liczby ze stosu - te się powtórzyły.

> > > Ci, co nie maja czasu sie zastanawiać nad algorytmem, nie
> > > mają czasu, bo potrzebują go zachować na długie obliczenia;-)
>
> > No dobrze, o ile lepszą można napisać funkcję hash od xorów
> > losowych liczby?
>
> Zalezy od danych. I od tego, co sie wylosuje;)
> W wiekszosci przypadków powinno być niezle.

By trzeba zsumować prawdopodobieństwo rozkładu
wymnożone przez jego złożoność... za ciężkie dla mnie.

Pesymistyczny przypadek:

Mamy N danych.
Mamy hash-table o rozmiarze M.
Kolizje rozwiązujemy przy pomocy drzew binarnych.

N danych w M-elementowej tablicy może rozłożyć się
na M^N sposobów.

Prawdopodobieństwo złożoności N * LOG( N ) :
Wszystkie dane muszą zostać zaadresowane na tą
samą komórkę hash-table, czyli M / M^N.
To się nie zdarzy nigdy :)

Może ktoś policzy do końca?
Pozdrawiam

do góry

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

do góry

On 10 Paź, 00:56, Michoo <m...@v...pl> wrote:

> Message-ID: <i8qnsn$21h$1@news.onet.pl>
Mogę poprosić o linka? Chętnie zobaczę, a jakoś nie mogę
się dokopać w onecie do tego postu.

Pozdrawiam i dzięki.

do góry

Mariusz Marszałkowski <m...@g...com> wrote:

> On 10 Paź, 00:56, Michoo <m...@v...pl> wrote:
>
> > Message-ID: <i8qnsn$21h$1@news.onet.pl>
> Mogę poprosić o linka? Chętnie zobaczę, a jakoś nie mogę
> się dokopać w onecie do tego postu.

http://42.pl/na lub
http://42.pl/na/i8qnsn$21h$...@n...onet.pl

do góry