Сортировка перестановок со знаками при помощи обращений (расстояние обращения): различия между версиями

Реализация алгоритма с линейным временем выполнения в виде программы на C доступна на странице www.cc.gatech.edu/~bader. Также доступны две другие реализации, разработанные для вычисления кратчайшей последовательности инверсий наряду с расстоянием. Одна из них принадлежит Ханненхалли и реализует его первый алгоритм [9], выполняющийся за квадратичное время при вычислении расстояний; Другая представляет собой Java-апплет, написанный Мантином (http://www.math.tau.ac.il/~rshamir/GR/) и реализующий клгоритм KST [10], но использующий явное представление графа перекрытий и в силу этого имеющий квадратичное время выполнения. Реализация Ханненхалли работает очень медленно; в ней применен исходный метод Ханненхалли и Певзнера, а не более быстрый – Бермана и Ханненхалли. Апплет KST также оказывается очень медленным из-за явного построения графа перекрытий.