Сложность применения перестановки на месте

К моему удивлению, я не смог найти статьи об этом - вероятно, искал не те ключевые слова.

Итак, у нас есть массив чего угодно и функция по его индексам; - перестановка.$f$$f$

Как переупорядочить массив в соответствии с с памятью и временем выполнения, максимально приближенными к и ?O ( 1 ) O ( n $f$$O(1)$$O(n)$

Существуют ли дополнительные условия, когда эта задача становится легче? Например, когда мы явно знаем, что функция является обратной к ?$g$$f$

Я знаю алгоритм, который следует за циклами и проходит цикл для каждого индекса, чтобы проверить, является ли он наименьшим в своем цикле, но опять же, он имеет время выполнения худшем случае , хотя в среднем он, кажется, ведет себя лучше ...$O(n^2)$

Вариант 0: Перестановка на месте (1995) Фейт Э. Фич, Дж. Ян Мунро, Патрисио В. Поблете время O ( log 2 n ) пространство.$O(n \log n)$$O( \log^{2} n )$

Вариант 1. Обман, сжимая вашу перестановку в краткую структуру данных, см. Munro http://www.itu.dk/people/ssrao/icalp03-a.pdf .

Вариант 2. Используйте разложение по простому циклу для краткого хранения перми и используйте это дополнительное место для обмана http://oeis.org/A186202

Вариант 3: отслеживание наибольшего индекса каждого цикла манипулирования. Для каждой итерации используйте самый большой невидимый индекс, чтобы переместить все в своем цикле на единицу. Если он попадает в видимый индекс, отмените всю эту работу, потому что цикл уже был изменен. время, O ( # циклов * log n ) пространство.$O(n^2)$$O(\#\text{cycles} * \log n)$

Вариант 4. Отслеживайте наибольший индекс каждого манипулируемого цикла, но делайте это только партиями с различной длиной цикла. Для каждой итерации используйте самый большой невидимый индекс, чтобы переместить все в цикле на единицу. Если он попадает в видимый индекс, отмените всю эту работу, потому что цикл уже был изменен. времени, O ( ( # циклов _ с _ одинаковым _ размером ) ∗ log n ) пробел.$O(n^2 * \text{distinct}\_\text{cycle}\_\text{lengths})$$O((\#\text{cycles}\_\text{with}\_\text{same}\_\text{size}) * \log n)$

Вариант 5: из той же бумаги Munro, что и вариант 0, для поверните цикл p ( i ), если i - самый большой индекс в этом цикле. O ( n 2 ) время и O ( log n ) пространство.$i = 1 .. n$$p(i)$$i$$O(n^2)$$O(\log n)$

Если вы используете представление циклов перестановки, вам потребуется 1 дополнительный элемент массива для хранения переставляемого элемента, и вы можете выполнять циклы в худших операциях O (N).

Любая перестановка из N элементов может быть преобразована в любую другую перестановку с использованием N-1 или менее обменов. В худшем случае для этого метода может потребоваться O (n ^ 2) вызовов вашего оракула, F (). Начните с наименьшей позиции. Позвольте x быть позицией, которую мы в настоящее время меняем.

Если F (x)> = x, то поменяйте местами позиции x и F (x). Иначе, мы должны найти, где элемент, который находился в позиции F (x), в настоящее время находится в списке. Мы можем сделать это с помощью следующей итерации. Пусть у = F (х). Do до y> = x: y = F (y): Конец Do. Теперь поменяйте позиции x и y.

Этот метод использует инверсию F и требует n бит памяти. Если x - это позиция элемента в исходном массиве, пусть G (x) - это позиция элемента в отсортированном массиве. Пусть B будет n-битным массивом. Установите все n битов B в 0.

FOR x = 1 до n-1: ЕСЛИ B (x) == 0 ТО: y = G (x): DO ДО x == y: поменять местами позиции x и y: B (y) = 1: y = G ( y): ЦИКЛ: ENDIF: ДАЛЕЕ X

Этот метод позволяет поменять элемент, находящийся в данный момент в позиции x, на конечную позицию элемента. Внутренний цикл заканчивается, когда правильный элемент переводится в положение x. Поскольку каждый своп перемещает по крайней мере один элемент в конечную позицию элемента, внутренний цикл Do не может выполнить более n-1 раз за цикл. Я думаю, что этот метод O (N) время и пространство.