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."

Jeśli dobrze rozumiem, chodzi o sprawdzenie czy wszystkie liczby w danym ciągu
są różne, czy też może którakolwiek z nich występuje w nim więcej niż raz.

Niby można rozwiązać to tak: posortować ciąg w czasie nlgn (np. Mergesortem),
a później, zaczynając od drugiego elementu ciągu, przejrzeć go liczba po
liczbie sprawdzając czy przypadkiem któraś wartość nie jest równa wartości
występującej tuż przed nią. Daje to żądany czas nlgn, ale czy rzeczywiście o
takie rozwiązanie chodziło autorowi? Zadanie pochodzi praktycznie z samego
początku książki, przed nim opisany jest jedynie algorytm sortowania przez
wstawianie działający w czasie kwadratowym, więc przy założeniu, że problem da
się rozwiązać bez wiedzy wykraczającej poza dotychczas przedstawioną teorię,
powołując się na opisane dalej sortowanie przez scalanie raczej nie znalazłem
rozwiązania, które "autor miał na myśli". A może zadania w tej książce są
jednak ułożone tak, że czasami trzeba do nich wracać dopiero po przeczytaniu
dalszych rozdziałów?

Pytanie do Was: jak Wy byście rozwiązali podany problem?



--
Wysłano z serwisu OnetNiusy: http://niusy.onet.pl