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

Бафна и Певзнер представили граф циклов для перестановки [3], ставший базовой структурой данных для вычисления расстояния инверсии. После этого Хамменхалли и Певзнер разработали базовую теорию для выражения расстояния инверсии в легко вычисляемых терминах (количество точек разрывов минус количество циклов плюс количество препятствий плюс поправочный коэффициент для укреплений [3, 15] – укрепления и препятствия можно легко обнаружить при помощи анализа связных компонентов). Они также предложили первый алгоритм с полиномиальным временем выполнения для сортировки подписанных перестановок при помощи обращений [9] и <math>O(n^4)</math>-реализацию этого алгоритма, которая в случае ограничения вычисления только расстоянием выполняется за квадратичное время. Этот алгоритм требует вычисления связных компонент графа перекрытий, что является узким местом при вычислении расстояний. Впоследствии Берман и Хамменхалли применили некоторые комбинаторные свойства графа циклов, получив алгоритм с временем выполнения <math>O(n \alpha(n))</math> для вычисления связных компонент и реализацию алгоритма сортировки с временем выполнения <math>O(n^2 \alpla(n))</math> [6], где <math>\alpha</math> – обратная функция Аккермана. (Более поздний алгоритм Каплана, Шамира и Тарьяна (Kaplan-Shamir-Tarjan, KST) [10] сокращает время выполнения, необходимое для вычисления кратчайшей последовательности инверсий, но использует тот же подход для вычисления длины этой последовательности).