4501
правка
Сортировка при помощи транспозиций и обращений (коэффициент аппроксимации 1,5): различия между версиями
Перейти к навигации
Перейти к поиску
Сортировка при помощи транспозиций и обращений (коэффициент аппроксимации 1,5) (посмотреть исходный код)
Версия от 15:08, 7 марта 2019
, 7 марта 2019→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 26: | Строка 26: | ||
'''Преобразование в 3-перестановки''' | '''Преобразование в 3-перестановки''' | ||
Перестановка называется ''простой'', если ее граф разрывов содержит только k-циклы, где <math>k \le 3</math>. Простая перестановка также называется ''3-перестановкой'', если она не содержит 2-циклов. Преобразование из ж в ж называется безопасным, если п(ж) — соаа(лг) = п{ж) — со^(ж). Было показано, что любая перестановка ж может быть преобразована в простую перестановку ж' при помощи безопасных преобразований и, более того, что любая сортировка ж' имитирует сортировку ж с тем же количеством операций [6, 11]. Хартман и Шаран [8] также показали, что любая простая перестановка ж' может быть преобразована в 3-перестановку ж при помощи безопасных операций заполнения (преобразующих эти 2-циклы в 1-скрученные 3-циклы) и, более того, что любая сортировка ж имитирует сортировку ж' с тем же количеством операций. Основываясь на этих двух свойствах, можно заключить, что произвольная перестановка ж может быть преобразована в 3-перестановку ж, такую, что любая сортировка ft имитирует сортировку ж с тем же количеством операций, предполагая, что можно ограничить рассмотрение только циклическими 3-перестановками. | |||
'''Типы циклов''' | |||