W dniu 09.10.2010 18:38, Mariusz Marszałkowski pisze:
> On 8 Paź, 21:16, "Piotrek"<p...@p...onet.pl> wrote:
>> Powoli zbieram się do uczciwego przeczytania "Wprowadzenia do algorytmów"
>> Cormena. W mojej wersji po rozdziale 1.2 znajduje się m.in. takie zadanie:
>>
>> "Rozważmy problem wykrywania powtarzających się elementów w ciągu n liczb
>> <x_1, x_2, ... , x_n>. Pokaż, że można rozwiązać ten problem w czasie
>> Theta(nlgn), gdzie lgn oznacza logarytm n przy podstawie 2."
>
>> Pytanie do Was: jak Wy byście rozwiązali podany problem?
>
> W czasie N, liniowy jednoprzebiegowy algorytm. Dodajemy do hash-
> table,
> a potem wyświetlamy te elementy które zostały dodane więcej niż jeden
> raz.
Łooo!

Rozumiem pisząc hashtable masz na myśli hashtable a nie hashtree (które
by przez swoją "drzewowatość" dawałoby nlog n).

A klasyczne hashtable o rozmiarze k realizowane funkcją modulo k wymaga
obsługi powtarzających się haszy. i te powtarzające się hasze będzie się
obługiwać albo w ulog u przy uży7ciu stosu/drzewa (gdzie u to ilość
haszy kolidujących) albo w u^2 przy naiwnej implementacji z listą.


--
Pozdrawiam
Michoo