4446
правок
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
Строка 9: | Строка 9: | ||
Пусть <math>\rho_1, ..., \rho_k</math> – последовательность обращений. Она сортирует перестановку | Пусть <math>\rho_1, ..., \rho_k</math> – последовательность обращений. Она сортирует перестановку <math>\pi</math>, если <math>\pi \cdot \rho_1 \cdot \cdot \cdot \rho_k = Id</math>, где Id = (1, ..., n) – тождественная перестановка. Длина кратчайшей последовательности обращений при сортировке ж называется ''расстоянием обращения'' <math>\pi</math> и обозначается как <math>d(\pi)</math>. | ||
Если вычисление | Если вычисление <math>d(\pi_</math> производится за линейное время [2] (см. статью «Расстояние обращений»), то вычисление последовательности размера <math>d(\pi)</math>, выполняющей сортировку <math>\pi</math>, является более сложным, и для него пока не разработано линейных алгоритмов. Наилучшие параметры сложности на данный момент демонстрирует решение Танье и Сагот [17], которое было теоретически улучшено в работах Танье, Бержерон и Сагот [18] и Хана [8]. | ||
== Основные результаты == | == Основные результаты == |
правок