1
Czy możemy skonstruować k-mądrą niezależną permutację na [n], używając tylko stałego czasu i przestrzeni?
Niech k>0k>0k>0 będzie stałą stałą. Biorąc pod uwagę liczbę całkowitą nnn , chcemy skonstruować permutację σ∈Snσ∈Sn\sigma \in S_n tak aby: Konstrukcja wykorzystuje stały czas i przestrzeń (tj. Wstępne przetwarzanie zajmuje stały czas i przestrzeń). Możemy użyć randomizacji. Biorąc pod uwagę i∈[n]i∈[n]i\in[n] , σ(i)σ(i)\sigma(i) można obliczyć w stałym czasie i przestrzeni. …