Сортировка перестановок со знаками при помощи обращений (последовательность обращений): различия между версиями

Вспомним, что существует линейный алгоритм для вычисления расстояния обращений по формуле <math>d(\pi) = n + 1 - c(\pi) + t(\pi)</math> (нотация из работы [4]), где <math>c(\pi)</math> – количество циклов в графе разрывов, а <math>t(\pi)</math> вычисляется из неориентированных компонентов перестановки, см. статью «Расстояние обращений»). После расчета этого показателя тривиальный алгоритм вычисляет последовательность размера <math>d(\pi)</math>: на очередном шаге алгоритма пробовать каждое возможное обращение p, до тех пор, пока не будет найдено такое, что <math>d(\pi \cdot \rho) = d(\pi) - 1</math>. Такое обращение называется ''безопасным''. Этот подход требует O(n) вычислений для каждого возможного обращения (они занимают не более <math>(n + 1)(n + 2)/2 = O(n^2))</math>; в результате итераций для поиска последовательности получаем алгоритм со сложностью <math>O(n^4)</math>.

Все опубликованные решения для вычисления последовательности сортировок делятся на две части, следуя разбиению формулы расстояния на два параметра: первый тип решений вычисляет последовательность обращений таким образом, что полученная перестановка не имеет неориентированных компонентов; второй тип сортирует все ориентированные компоненты.