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