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

Вспомним, что существует линейный алгоритм для вычисления расстояния обращений по формуле d{n) = n + 1 — с{ж) + фг) (нотация из работы [ ]), где с(ж) – количество циклов в графе разрывов, а фг) вычисляется из неориентированных компонентов перестановки (см. статью «Расстояние обращений»). После расчета этого показателя тривиальный алгоритм вычисляет последовательность размера d(jr): на очередном шаге алгоритма пробовать каждое возможное обращение p, до тех пор, пока не будет найдено такое, что d(ж ■ p) = сфг) - 1. Такое обращение называется безопасным. Этот подход требует O(n) вычислений для каждого возможного обращения (они занимают не более (n + 1)(n + 2)/2 = O(n2)); в результате итераций для поиска последовательности получаем алгоритм со сложностью O(n4).