Łatwo zauważyć, że dla dowolnego istnieje odwzorowanie 1-1 z {0,1} na {0,1} takie, że dla dowolnego wektor jest „zbalansowany”, tzn. ma równą liczbę 1 i 0. Czy jest możliwe zdefiniowanie takiego , aby przy danym można było skutecznie obliczyć ?F n n + O ( log n ) x F ( x ) F x F ( x )
Dzięki.
Odpowiedzi:
Rozważmy bitowe łańcuchy . Definicje:xn x
Teraz napraw ciąg . Rozważ funkcję . Obserwacje:g ( i ) = b ( f ( x , i ) )x g(i)=b(f(x,i))
Wynika z tego, że istnieje taki, że .- 1 ≤ g ( i ) ≤ + 1i −1≤g(i)≤+1
Stąd możemy skonstruować -bitowy ciąg w następujący sposób: konkatenować i binarne kodowanie indeksu . Bezwzględna wartość niezbilansowania wynosi . Co więcej, możemy odzyskać biorąc pod uwagę ; mapowanie jest bolesne.y f ( x , i ) i y O ( log n ) x y(n+O(logn)) y f(x,i) i y O(logn) x y
Na koniec możesz dodać bity pozorne które zmniejszają nierównowagę z do .y O ( log n ) 0O(logn) y O(logn) 0
źródło
źródło