4446
правок
Сортировка перестановок со знаками при помощи обращений (последовательность обращений): различия между версиями
Перейти к навигации
Перейти к поиску
м
Сортировка перестановок со знаками при помощи обращений (последовательность обращений) (посмотреть исходный код)
Версия от 15:34, 22 февраля 2019
, 22 февраля 2019→Основные результаты
Irina (обсуждение | вклад) мНет описания правки |
Irina (обсуждение | вклад) |
||
| Строка 28: | Строка 28: | ||
Лучшее решение для первой части предложили Каплан, Шамир и Тарьян [ ]; их алгоритм выполняется за линейное время при сочетании с линейным алгоритмом вычисления расстояния [2], он основан на ранних находках Ханненхалли и Певзнера [ ]. | Лучшее решение для первой части предложили Каплан, Шамир и Тарьян [10]; их алгоритм выполняется за линейное время при сочетании с линейным алгоритмом вычисления расстояния [2], он основан на ранних находках Ханненхалли и Певзнера [9]. | ||
Вторая часть представляет собой «узкое место» всей процедуры. На этот момент неориентированных компонентов уже не осталось, расстояние составляет d( | Вторая часть представляет собой «узкое место» всей процедуры. На этот момент неориентированных компонентов уже не осталось, расстояние составляет <math>d(\pi) = n + 1 - c(\pi)</math>, так что безопасным обращением будет являться такое, которое увеличивает <math>c(\pi)</math> и не создает неориентированных компонентов (это увеличило бы <math>t(\pi)</math>). | ||
Обращение, увеличивающее <math>t(\pi)</math>, называется ''ориентированным''. Найти ориентированное обращение несложно: его определяют любые два последовательных числа в перестановке, имеющих разные знаки. Гораздо сложнее убедиться в том, что это действие не увеличивает число неориентированных компонентов. | |||
Квадратичные алгоритмы, разработанные, с одной стороны, Берманом и Ханненхалли [5], а с другой – Капланом, Шамиром и Тарьяном [10], основаны на распознавании безопасных обращений за линейное время. На данный момент не известно улучшенных алгоритмов распознавания безопасных обращений, и представляется, что нижняя граница уже была достигнута, о чем свидетельствуют Озери-Флато и Шамир в работе [14], в которой они сообщили, что «главный вопрос в исследованиях перестановок геномов заключается в том, можно ли получить субквадратичный алгоритм для сортировки при помощи обращений». Этот алгоритм был получен Танье и Сагот [17], которые доказали, что распознавание безопасного обращения на каждом этапе не является необходимым; требуется только распознавание ориентированные обращений. | |||
Алгоритм основан на следующей теореме, приведенной в работе [18]. Последовательность ориентированных обращений <math>\rho_1, ..., \rho_k</math> называется ''максимальной'', если не существует ориентированного обращения в <math>\pi \cdot \rho_1 \cdot \cdot \cdot \rho_k</math>. В частности, последовательность сортировки является максимальной, в то же время обратное неверно. | |||
Теорема 1. Если последовательность S является максимальной, но не является последовательностью сортировки ориентированных обращений для перестановки, то существует непустая последовательность | |||
Теорема 1. Если последовательность S является максимальной, но не является последовательностью сортировки ориентированных обращений для перестановки, то существует непустая последовательность S' ориентированных обращений, такая, что S может быть разбита на две части <math>S = S_1, S_2</math>, и <math>S_1, S', S_2</math> является последовательностью ориентированных обращений. | |||
| Строка 47: | Строка 48: | ||
Этот алгоритм, с классической структурой данных для представления перестановок (например, в виде массива), также имеет сложность O( | Этот алгоритм, с классической структурой данных для представления перестановок (например, в виде массива), также имеет сложность <math>O(n^2)</math>, поскольку на каждом этапе он должен провести проверку на наличие ориентированного обращения и применить его к перестановке. | ||
Небольшая модификация структуры данных, предложенная Капланом и Вербином [ ], позволяет выбирать и применять ориентированное обращение за время O(n log n); с ее помощью алгоритм Танье-Сагот достигает временной сложности O(n3/2plog n). | Небольшая модификация структуры данных, предложенная Капланом и Вербином [11], позволяет выбирать и применять ориентированное обращение за время O(n log n); с ее помощью алгоритм Танье-Сагот достигает временной сложности O(n3/2plog n). | ||