On 2012-11-24, slawek <s...@h...pl> wrote:
> Nie jest. Oczywiście - sortowanie to w pewnym sensie "brute force" - da się
> i sortując a potem zliczając, tyle że nie wydaje się, aby to był najlepszy
> algorytm (delikatnie rzecz ujmując).

Bo to nie jest docelowy algorytm (choć może być). To jest tylko pewne
oszacowanie złożoności problemu.

Algorytmów do takiego problemu można wymyślić dużo (wiadomo ile).
Oczywiście sortowanie explicite można zastąpić drzewami, ale de facto
sprowadza się to do podobnych operacji. Dlatego napisałem, że jest to
równoważne sortowaniu (bo trzeba te elementy porównać i jakoś umożliwić
szybkie odwoływanie się do już "zaliczonych", a o to właśnie chodzi
w sortowaniu). Kolejnym podejściem jest hash'owanie.

Jeśli zakładasz, że po danych możesz przejść tylko raz i nie możesz
ich wszystkich zapisać, bo analizujesz "na żywo" (standardowa sytuacja
w fizyce, więc może to właśnie Cię dotyczy), to musisz przechowywać
zliczenia historyczne (przynajmniej tych elementów, które jeszcze mogą
"wygrać"). To jest po prostu nie do przeskoczenia w ogólnym przypadku.

pozdrawiam,
PK