Пусть <texwikitex> Пусть $ P = (p_1,p_2,\dots,p_n)</tex> $ является [[Действие перестановки на набор из элементов, представление в виде циклов|перестановкой]] чисел <tex> $ 1, 2,\dots, n</tex>$.
{{Определение
|definition =
'''Инверсией''' в перестановке <tex>$P</tex> $ называется всякая пара индексов <tex>$i, j</tex> $ такая, что <tex>$1\leqslant i<j\leqslant n</tex> $ и <tex>$P[i]>P[j]</tex>$.
}}
{{Определение
|definition =
'''Таблицей инверсий''' перестановки <tex> $ P </tex> $ называют такую последовательность <tex> $ T = (t_1,t_2,\dots,t_n)</tex>$, в которой <tex>$t_i</tex> $ равно числу элементов перестановки <tex> $ P </tex>$, стоящих в <tex> $ P </tex> $ левее числа <tex>$i</tex> $ и больших <tex>$i</tex>$.
}}
== Алгоритмы = Алгоритм построения/восстановления == = Таблицу инверсий тривиально построить по определению. Для каждого элемента перестановки считаем количество элементов, больших данного и стоящих в перестановке левее него.Алгоритм построения в псевдокоде выглядит так: $T[1..n] = 0$ $For$ $i = 1..n$ $For$ $j = 1..(i - 1)$ $if$ $P[j] > P[i]$ $T[P[i]] = T[P[i]] + 1$Сложность данного алгоритма {{---}} $O(n^2)$. Уменьшить время работы можно используя [[Дерево отрезков. Построение|дерево отрезков]].
Ниже описанные алгоритмы работают за время О(n^2)Отсортируем элементы перестановки, но их можно ускорить до О(сохраняя индексы. Массив $M$ будет содержать номер позиции каждого элемента в исходной перестановке. Также заведём массив $S$ длиной $n*log(n)) ускорив процесс поиска$, например двоичными деревьямиинициализированный нулями. === Алгоритм построения === Для получения таблицы инверсий из таблицы перестановки вводим таблицу равной по длине таблице перестановки(не умаляя общности длина равна n) и на nПосле обработки $i$-ное место записываем 0; ищем число го элемента будем вносить значение 1 в ячейку $S[M[i ]]$. Обработку начинаем с последнего элемента и двигаемся к началу. Пусть, функция $Sum(i)$ возвращает значение суммы элементов массива $S$ от n-1 до 1) в таблице перестановки, и смотрим: сколько чисел больше $i$ включительно. Тогда $i $-й элемент таблицы инверсий находится слева от числа так: $T[i, полученное число записываем в таблицу инверсий на ] = Sum(M[i-тое место])$ Функция Sum реализуется с помощью [[Дерево отрезков. Построение|дерева отрезков]]. Каждое изменение массива и обращение к функции $Sum$ влечёт за собой $log_2 n$ операций.Таким образом получаем сложность алгоритма $O(n*log_2 n)$
=== Алгоритм восстановления ===
[2 3 6 4 0 2 2 1 0] - т. инверсии
|-}
</wikitex>
