On 20.11.2012 18:23, slawek wrote:

> Aby nie być posądzanym o niekonstruktywną krytykę zapodam przykład (ktoś
> chciał informatycznych wyzwań, żeby coś ciekawego było itd.) - to takie
> zadanko:

W ten sposób usunąłeś z zadanka jeden z ciekawych elementów, czyli "o co
tu chodzi".

>
> "Dany jest plik długości 2 gigabajtów (tj. 2*1024*1024*1024). Wśród
> wszystkich możliwych podciągów 16-bajtowych (których jest 2**31 - 2^4 +
> 1, bo wybieramy kolejne bajty) znaleźć taki, który najczęściej występuje
> w tym pliku. Uwaga: dane w pliku /mogą/ być zupełnie przypadkowe, może
> też cały plik być wypełniony zerami itd. itp. - wszystkie złośliwe
> przypadki dozwolone - tzn. nie wolno zgadywać, trzeba sprawdzić.
> Premiowane będą rozwiązania szybkie i oszczędzające pamięć (zakładamy że
> mamy tylko 512 MB RAM do dyspozycji)."

Mamy problem znalezienia dominanty w zbiorze liczb 16 bajtowych. Jeżeli
dobrze szacuję (a nie chce mi się poświęcać na to zadanko za dużo czasu):
- dla działania w miejscu mamy O(n^2)
- dla dodatkowej pamięci na dysku w rozmiarze 16*n schodzimy do
O(n*log(n)) (Ale z uwzględnieniem losowych odwołań do dysku)
- dla dodatkowej pamięci na dysku w rozmiarze 2*16*n schodzimy do
O(n*log(n)) (Z sekwencyjnym dostępem, więc wielokrotnie szybciej niż w
poprzednim przypadku.)

n to oczywiście liczba liczb w ciągu

--
Pozdrawiam
Michoo