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

Если вычисление <math>d(\pi_</math> производится за линейное время [2] (см. статью «Расстояние обращений»), то вычисление последовательности размера <math>d(\pi)</math>, выполняющей сортировку <math>\pi</math>, является более сложным, и для него пока не разработано линейных алгоритмов. Наилучшие параметры сложности на данный момент демонстрирует решение Танье и Сагот [17], которое было теоретически улучшено в работах Танье, Бержерон и Сагот [18] и Хана [8].