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

Небольшая модификация структуры данных, предложенная Капланом и Вербином [11], позволяет выбирать и применять ориентированное обращение за время O(n log n); с ее помощью алгоритм Танье-Сагот достигает временной сложности O(n3/2plog n).

Недавно Хан [8] предложил еще одну структуру данных, позволяющую выбирать и применять ориентированное обращение за время O(pn); аналогичная небольшая модификация, вероятно, поможет снизить сложность алгоритма в целом до O(n3/2).

Почти все исследования последовательностей сортировки для обращений были ориентированы на выдачу строго одной последовательности, хотя было замечено, что нередко этих последовательностей оказывается много (даже для n < 10 их может быть несколько миллионов). Лишь несколько исследований попытались восполнить этот пробел.

Алгоритм перечисления всех безопасных обращений на одном этапе был предложен и реализован Сипелем [16]. Структуру пространства оптимальных решений открыли Шаве и др. [ ]; алгоритмические подходы к этой структуре исследовались в работе [6].