Существует ли структура данных для эффективной реализации этого алгоритма шифрования?

Question

ввод -> алфавит -> вывод (индекс числа в алфавите) -> новый алфавит (число, перенесенное в начало алфавита):

3 -> [1, 2, 3, 4, 5] -> 3 -> [3, 1, 2, 4, 5]

2 -> [3, 1, 2, 4, 5] -> 3 -> [2, 3, 1, 4, 5]

1 -> [2, 3, 1, 4, 5] -> 3 -> [1, 2, 3, 4, 5]

1 - > [1, 2, 3, 4, 5] -> 1 -> [1, 2, 3, 4, 5]

4 -> [1, 2, 3, 4, 5] -> 4 -> [4, 1, 2, 3, 5]

5 -> [4, 1, 2, 3, 5] -> 5 -> [5, 4, 1, 2, 3]

ввод: (n - количество цифр в алфавите, m - длина текста, который должен быть зашифрован, текст)

5, 6

3 2 1 1 4 5

Ответ: 3 2 1 1 4 5 -> 3 3 3 1 4 5

Существует ли какая-либо структура данных или алгоритм, позволяющий сделать это эффективно, быстрее, чем O (n * m)?

Буду признателен за любые идеи. Спасибо.

Answer 1

Используйте дерево статистики порядка для хранения пар (1,1)...(n,n), упорядоченных по первым элементам.

Найдите перевод для символа c, выбрав c -мый наименьший элемент дерева и его второй элемент.

Затем обновите дерево, удалив найденный вами узел, и вставьте его обратно в дерево с первым элементом пары, установленным в -t где t - это позиция в сообщении (или некотором другом постоянно уменьшающемся счетчике).

Поиск, удаление и вставка могут быть выполнены в O(ln n) худшем случае времени, если самообалансированное дерево поиска ( например, красно-черное дерево ) используется в качестве базовой структуры дерева для дерева статистики заказов.

Учитывая, что элементы для исходного дерева вставляются в порядке, можно построить структуру дерева в O(n).

Таким образом, весь алгоритм будет O(n + m ln n) время, наихудший случай.

---

Вы можете дополнительно улучшить это для случая, когда n больше, чем m, сохраняя только один узел для любого непрерывного диапазона узлов в дереве, но считая его с целью ранга в дереве статистики заказов в соответствии с числом узлов в нем будет обычно равным.

Начиная затем только с одного фактически сохраненного узла, когда дерево переставляется, вы разделяете узел, представляющий диапазон, на три: один узел, представляющий диапазон до найденного значения, один, представляющий диапазон после найденного значения, и один, представляющий фактическое значение , Эти три узла затем вставляются обратно, в случае узлов диапазона, только если они не пустые, а первый элемент пары равен второму, а в случае узла недиапазона - с отрицательным значением, как описано выше. Если найден узел с отрицательной первой записью, он не разбивается на это.

В результате дерево будет содержать не более O(m) узлов, поэтому алгоритм имеет наихудшую сложность времени: O(m ln min(n,m)).

Answer 2

Может быть, хэш-карта с парами букв и индексов? Я полагаю, что поиск элементов в хэш-карте обычно выполняется O (1) в большинстве случаев, если только у вас нет коллизий (что маловероятно).