Сортировка перестановок со знаками при помощи обращений (расстояние обращения): различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) мНет описания правки |
Irina (обсуждение | вклад) мНет описания правки |
||
| Строка 6: | Строка 6: | ||
Поиск расстояния инверсии представляет собой сложную вычислительную задачу, активно изучавшуюся в последние годы [1, 4, 6, 7, 8, 9, 10]. Задача поиска расстояния инверсии между перестановками без знаков является NP-трудной [7], в то же время для | Поиск расстояния инверсии представляет собой сложную вычислительную задачу, активно изучавшуюся в последние годы [1, 4, 6, 7, 8, 9, 10]. Задача поиска расстояния инверсии между перестановками без знаков является NP-трудной [7], в то же время для перестановок со знаками она может быть решена за линейное время [1]. | ||
== Основные результаты == | == Основные результаты == | ||