On 2012-11-24, Michoo <m...@v...pl> wrote:
> 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)

Da się lepiej.

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

Mówiąc inaczej. Zaproponowany problem jest de facto równoważny
posortowaniu zbioru wejściowego.

pozdrawiam,
PK