4446
правок
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
Строка 51: | Строка 51: | ||
Небольшая модификация структуры данных, предложенная Капланом и Вербином [11], позволяет выбирать и применять ориентированное обращение за время O(n log n); с ее помощью алгоритм Танье-Сагот достигает временной сложности O( | Небольшая модификация структуры данных, предложенная Капланом и Вербином [11], позволяет выбирать и применять ориентированное обращение за время <math>O(\sqrt{n \; log \; n})</math>; с ее помощью алгоритм Танье-Сагот достигает временной сложности <math>O(n^{3/2} \sqrt{log \; n})</math>. | ||
Недавно Хан [8] предложил еще одну структуру данных, позволяющую выбирать и применять ориентированное обращение за время O( | Недавно Хан [8] предложил еще одну структуру данных, позволяющую выбирать и применять ориентированное обращение за время <math>O(\sqrt{n})</math>; аналогичная небольшая модификация, вероятно, поможет снизить сложность алгоритма в целом до <math>O(n^{3/2})</math>. | ||
'''Пространство оптимальных решений''' | '''Пространство оптимальных решений''' | ||
Почти все исследования последовательностей сортировки для обращений были ориентированы на выдачу строго одной последовательности, хотя было замечено, что нередко этих последовательностей оказывается много (даже для n < | Почти все исследования последовательностей сортировки для обращений были ориентированы на выдачу строго одной последовательности, хотя было замечено, что нередко этих последовательностей оказывается много (даже для <math>n \le 10</math> их может быть несколько миллионов). Лишь несколько исследований попытались восполнить этот пробел. | ||
Алгоритм перечисления всех безопасных обращений на одном этапе был предложен и реализован Сипелем [16]. Структуру пространства оптимальных решений открыли Шаве и др. [ ]; алгоритмические подходы к этой структуре исследовались в работе [6]. | Алгоритм перечисления всех безопасных обращений на одном этапе был предложен и реализован Сипелем [16]. Структуру пространства оптимальных решений открыли Шаве и др. [3]; алгоритмические подходы к этой структуре исследовались в работе [6]. | ||
== Применение == | == Применение == |
правок