On 9 Paź, 21:35, Michoo <m...@v...pl> wrote:
> 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ą.

No dobra, ale po co brać pod uwagę pesymistyczny przypadek który
zdarza się tak rzadko, że ciężko policzyć? To się w praktyce dla
dużych danych nie zdarzy, a dla małych najszybciej zadziała algorytm o
małym narzucie liniowym.
Pozdrawiam