On 2012-11-24, slawek <s...@h...pl> wrote:
>> Mówiąc inaczej. Zaproponowany problem jest de facto równoważny
>> posortowaniu zbioru wejściowego.
>
> Nie jest.
>
> 1. Dla pliku 1GB i 16 bajtowych "sekwencji" musiałbyś najpierw wygenerować
> plik 16 GB i dopiero potem go sortować. Czyli z N, M robi się N*M. W
> mikroskali:

"Równoważny" nie oznacza, że trzeba posortować to wejście. Chodzi tylko
o klasę problemów i klasę złożoności. W szczególności: rozwiązanie
Twojego problemu będzie miało złożoność nie mniejszą niż sortowanie,
więc nie da się go rozwiązać przy narzuconych przez Ciebie
ograniczeniach.

> różnych być może jeszcze mniej, a zawsze znacznie mniej niż liczb M-bitowych
> (których jest 2^M). A "naprawdę pamiętać" wystarczy tylko najlepszy
> rezultat.

Och zdecydowanie nie. Wariant pesymistyczny: dominantą w zbiorze jest
element, który występuje na pierwszym i na X ostatnich elementów (X
odpowiednio duże).
Dominanta jest statystyką upierdliwą, bo prawie zawsze trzeba brać
pod uwagę cały zbiór wartości. Algorytmy upraszczające wchodzą w grę
wtedy, gdy element występuje naprawdę często (np. stanowi połowę
wszystkich).

pozdrawiam,
PK