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

Пусть <math>\rho_1, ..., \rho_k</math> – последовательность обращений. Она сортирует перестановку ж, если ж ■ p\ ■ ■ ■ k = Id, где Id = (1; : : : ; n) – тождественная перестановка. Длина кратчайшей последовательности обращений при сортировке ж называется расстоянием обращения я и обозначается как d(jr).

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