1
Obliczanie parzystości permutacji w sposób strumieniowy
Szukam algorytmu jednoprzebiegowego, który oblicza parzystość permutacji. Zakładam, że permutacja wejściowa jest podawana przez strumień . Wyjście powinno być parzystością permutacji. Pytanie mnie interesuje, ile pamięci powinien użyć algorytm deterministyczny. Czy istnieje jakiś losowy algorytm dotyczący problemu?π[1],π[2],⋯,π[n]π[1],π[2],⋯,π[n]\pi[1], \pi[2], \cdots, \pi[n] Wiem, że obliczanie liczby inwersji w jednym przebiegu wykorzystuje pamięć …