64
правки
Изменения
Нет описания правки
Функция $Sum$ реализуется с помощью [[Дерево отрезков. Построение|дерева отрезков]]. Каждое изменение массива и обращение к функции $Sum$ влечёт за собой $\log_2n$ операций. Таким образом получаем сложность алгоритма $O(n\log_2n)$
Также существует достаточно простой алгоритм построения таблицы инверсий с использованием [[Сортировка слиянием|сортировки слиянием]]. Вначале выписываются следующие упорядоченные пары чисел: в $i$-ой паре на первом месте стоит $i$-й элемент перестановки, а на втором {{---}} 0. Далее применяется [[Сортировка слиянием|сортировка слиянием]], при чем при выписывании элемента из второй цепочки упорядоченных пар, число на второй позиции в данном элементе увеличивается на количество элементов, оставшихся в первой цепочке. В конце сортировки получим цепочку упорядоченных пар. Выписывая вторые элементы данных упорядоченных пар, получим искомую таблицу инверсий. Сложность данного алгоритма совпадает со сложностью [[Сортировка слиянием|сортировки слиянием]] и составляет $O(n\log_2n)$.
= Алгоритм восстановления =
