304
правки
Изменения
Нет описания правки
'''Инверсией''' в перестановке <tex>P</tex> называется всякая пара индексов <tex>i, j</tex> такая, что <tex>1\leqslant i<j\leqslant n</tex> и <tex>P[i]>P[j]</tex>.
}}
{{Определение
|definition =
}}
== Алгоритм построения ==
Таблицу инверсий тривиально построить по определению. Для каждого элемента перестановки считаем количество элементов, больших данного и стоящих в перестановке левее него.
Сложность представленного алгоритма есть <tex>O(n\log n)</tex>. Алгоритм с такой же сложностью можно построить с помощью дерева отрезков.
== Алгоритм восстановления ==
Для восстановления перестановки по таблицы инверсий <tex>T</tex> воспользуемся следующим соображением: единица стоит на <tex>T_i</tex>-ом месте (индексируем элементы с нуля), так как остальные числа в перестановке больше единицы. Далее, если известны расположения всех чисел <tex>1, \dots, k</tex>, то число <tex>k + 1</tex> стоит на <tex>T_{k + 1}</tex>-ой ещё не занятой позиции: все числа, меньшие <tex>k + 1</tex> уже расставлены. Это рассуждение напрямую переписывается в код следующим образом:
Этот алгоритм имеет сложность <tex>O(n \log n)</tex>: делается <tex>n</tex> итераций цикла, в которой происходит спуск по дереву высоты <tex>O(\log n)</tex> и один запрос на дереве отрезков. Таким образом, время работы алгоритма на каждой итерации есть <tex>O(\log n)</tex>.
== Пример == Рассмотрим пример построения таблицы инверсий и восстановления перестановки по таблице инверсий. Пусть дана перестановка <tex>(5, 7, 1, 3, 4, 6, 8, 2)</tex>. {| style = "border-style: solid; border-color: gray; text-align: center" cellpadding = "2" border = "1"|(5, 0)| (7, 0)| (1, 0)| (3, 0)| (4, 0)| (6, 0)| (8, 0)| (2, 0)|-|colspan = "2"|(5, 0), (7, 0)|colspan = "2"|(1, 0), (3, 0)|colspan = "2"|(4, 0), (6, 0)|colspan = "2"|(2, 1), (8, 0)|-|colspan = "4"|(1, 2), (3, 2), (5, 0), (7, 0)|colspan = "4"|(2, 3), (4, 0), (6, 0), (8, 0)|-|colspan = "8"|(1, 2), (2, 6), (3, 2), (4, 2), (5, 0), (6, 1), (7, 0), (8, 0)|} Полученная таблица инверсий: <tex>(2, 6, 2, 2, 0, 1, 0, 0)</tex>. Восстановим перестановку по таблице инверсий {| border = 1 cellpadding = "3"| || || '''1''' || || || || || || пропускаем две свободных позиции и ставим 1|-| || || 1 || || || || '''2''' || || пропускаем шесть свободных позиций и ставим 2|-| || || 1 || '''3''' || || || 2 || || пропускаем две свободных позиции и ставим 3|-| || || 1 || 3 || '''4''' || || 2 || || пропускаем две свободных позиции и ставим 4|-| '''5''' || || 1 || 3 || 4 || || 2 || || не пропускаем свободных позиции и ставим 5|-| 5 || || 1 || 3 || 4 || '''6''' || 2 || || пропускаем одну свободную позицию и ставим 6|-| 5 || '''7''' || 1 || 3 || 4 || 6 || 2 || || не пропускаем свободных позиций и ставим 7|-| 5 || 7 || 1 || 3 || 4 || 6 || 2 || '''8''' || не пропускаем свободных позиций и ставим 8|} == Источники ==
* Д. Кнут - Искусство программирования, том 3.
