Количество инверсий в последовательности — показатель того, насколько последовательность отсортирована. Например, в неубывающей последовательности не будет инверсий, а последовательность в порядке убывания содержит $n(n-1)/2$ инверсий (каждые два элемента образуют инверсию).
Решая задачу «Количество инверсий», примитивный алгоритм просматривает все возможные пары $(i,j)$, что требует времени выполнения $O(n^2)$. Чтобы решить эту задачу за время $O(n\log n)$ с помощью алгоритма «разделяй и властвуй», мы разделяем вводный массив на две половины и делаем рекурсивный вызов обоих из них. Остаётся только вычислить количество инверсий, которые образованы двумя элементами из разных частей. Если делать это примитивным образом, то мы снова придём к времени выполнения $O(n^2)$, так как общее количество таких пар составляет $\frac{n}{2} \cdot \frac{n}{2}=\frac{n^2}{4}=O(n^2)$. Оказывается, что если обе части уже отсортированы, количество инверсий из элементов разных половин можно вычислить за время $O(n)$. Это подсказывает нам, что вместо решения изначальной задачи, нам стоит решить более общую: вычислить количество инверсий в заданном массиве и в то же время отсортировать его.
✒️ Упражнение:
Измените алгоритм MergeSort
для решения этой задачи.
- Формат ввода: Первая строка содержит целое число $n$, следующая — последовательность целых чисел $a_0, \dotsc, a_{n-1}$.
- Формат вывода: Количество инверсий в последовательности.
- Ограничения: $1 \le n \le 30,000$, $1 \le a_i \le 10^9$ для всех $0 \le i \le n-1$.
Пример:
Ввод | Вывод |
---|---|
5 2 3 9 2 9 | 2 |
В примере две инверсии: $(2,4)$ ($a_2=3 > 2=a_4$) и $(3,4)$ ($a_3=9 > 2=a_4$).
Совет: используйте полуоткрытые интервалы для рекурсивных реализаций
Решение
Попробуем использовать самый распространённый подход к методу «разделяй и властвуй»: разделим вводную последовательность на две половины, LeftHalf
и RightHalf
, и выполним рекурсивный вызов для каждой. Это позволит нам вычислить все инверсии, находящиеся в одной и той же половине. Однако это не подскажет нам количество разделённых инверсий, то есть количество пар $(a_i,a_j)$, при которых $a_i$ находится в левой половине, $a_j$ находится в правой, а $a_i > a_j$.
💡 Остановитесь и подумайте:
Возьмём элемент $x$ в $LeftHalf$. Каково количество разделённых инверсий, в которые входит $x$?
Даны массив $List$ и целое число $x$. Пусть $List_x$ будет количеством элементов $List$, которые меньше $x$. Так как ответ на вопрос выше — это $RightHalf_x$, наша задача заключается в том, чтобы быстро вычислить $List_x$. Таким образом, мы приходим к следующей задаче: имея последовательность целых чисел $List$ и целое число $x$, нам нужно найти в $List$ количество элементов, которые меньше $x$. В случае неотсортированного массива это можно сделать за время $O(|List|)$, так как необходимо проверить каждый элемент массива. В варианте же отсортированного за время $O(\log |List|)$, если использовать двоичный поиск.
✒️ Упражнение:
Продемонстрируйте, как реализовать метод CountSmaller(List, x)
для подсчёта количества элементов $List$ со значением меньше $x$ за время $O(\log_2|List|)$.
Так мы приходим к следующему алгоритму «разделяй и властвуй».
CountInversions(List):
if ∣List∣ <= 1:
return 0
inversions = 0
// в случае нечётной длины
// центральный элемент может быть и слева, и справа
LeftHalf = левая половина List
RightHalf = правая половина List
inversions = inversions + CountInversions(LeftHalf)
inversions = inversions + CountInversions(RightHalf)
sort(RightHalf) // необходимо для двоичного поиска
for x in LeftHalf:
inversions = inversions + CountSmaller(RightHalf,x)
return inversions
Время выполнения $T(n)$ (где $n$ — длина $List$) удовлетворяет рекуррентному соотношению
Слагаемое $O(n\log n)$ включает в себя два шага: сортировку $RightHalf$ и ответ на $n/2$ запросов CountSmaller
. Эту рекуррентное соотношение нельзя напрямую вставить в основную теорему о рекуррентных соотношениях, так как элемент $O(n\log n)$ не имеет форму $O(n^d)$ при константе $d$. Однако мы можем проанализировать её таким же образом: рекурсивное дерево содержит $\log_2 n$ уровней, общий размер всех задач на каждом уровне равен $n$, а общее затраченное время на каждом уровне составляет $O(n\log n)$. В итоге общее время выполнения составляет $O(n\log^2n)$. Вместо того, чтобы формально это доказывать, мы улучшим вышеприведённый алгоритм так, чтобы он затрачивал время $O(n\log n)$.
Можно быстро найти все разделённые инверсии, если наряду с подсчётом инверсий сортировать входную последовательность. То есть можно предположить, что алгоритм CountInversionsAndSort(List)
возвращает количество инверсий в $List$ и сортирует $List$. После двух рекурсивных вызовов обе половины $List$ отсортированы. На данном этапе нам нужно сделать две вещи: отсортировать всю последовательность $List$ и вычислить количество разделённых инверсий. Мы уже знаем, как достичь первой цели: этим занимается процедура $Merge$. Это выглядит следующим образом. Пусть $l$ и $r$ будут первыми элементами отсортированных последовательностей $LeftHalf$ и $RightHalf$. Далее выбирается самый маленький из них и перемещается в увеличивающийся отсортированный список.
💡 Остановитесь и подумайте:
Можете ли вы найти количество разделённых инверсий, которые образует перемещаемый элемент?
Рассмотрим два случая.
- $l \le r$. В этом случае $l$ не больше каждого элемента $RightHalf$, и поэтому не образует разделённых инверсий.
- $l > r$. В этом случае $r$ меньше всех элементов $LeftHalf$, и поэтому образует разделённую инверсию с каждым из них.
Это приводит нас к следующему расширению метода Merge
.
Merge(LeftHalf, RightHalf):
SortedList = empty list
inversions = 0
while both LeftHalf and RightHalf are non-empty:
l = первый элемент LeftHalf
r = первый элемент RightHalf
if l <= r:
переместить l в SortedList
l = следующий элемент в LeftHalf
else:
переместить r в SortedList
r = следующий элемент в RightHalf
// учитываются только не перемещенные элементы
inversions = inversions + ∣LeftHalf∣
добавить все оставшиеся элементы LeftHalf и RightHalf в SortedList
return SortedList, inversions
И окончательная версия алгоритма CountInversions
.
CountInversions(List):
// список List будет отсортирован
if ∣List∣ <= 1:
return 0
LeftHalf = левая половина List
RightHalf = правая половина List
leftInv = CountInversions(LeftHalf)
rightInv = CountInversions(RightHalf)
List, splitInv = Merge(LeftHalf, RightHalf)
return leftInv + rightInv + splitInv