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