64
правки
Изменения
Нет описания правки
Приведём алгоритм восстановления с использованием [[Сортировка слиянием|сортировки слиянием]], имеющий сложность $O(n*log_2 n)$.
Пусть $\alpha$ и $\beta$ - цепочка цепочки упорядоченных пар целых неотрицательных чисел $[m_1, n_1]...[m_k, n_k]$. Рассмотрим двоичную операцию $o$, рекурсивно определенную на парах таких цепочек следующим образом:
$([m, n]\alpha)o([m', n']\beta)=\left\{\begin{aligned}[]
[m,n](\alpha o ([m'-m, n']\beta)), m \le m',\\
\right.$
Сопоставим каждому элементу таблицы инверсий его номер. Получится множество упорядоченных пар чисел $[m_1, n_1]...[m_k, n_k]$, где $mm_i$ {{- --}} сам элемент, а $nn_i$ {{--- }} его номер. Разобьем данные элементы на пары и произведём с ними операцию $o$. Получим некоторое количество цепочек упорядоченных пар. Также разбиваем их на пары и производим операцию $o$. Так действуем, пока не останется одна цепочка. Выписывая вторые элементы данных упорядоченных пар в том порядке, в каком они представлены в цепочке, получим первоначальную перестановку.
== Пример ==
