Количество инверсий в последовательности — показатель того, насколько последовательность отсортирована. Например, в неубывающей последовательности не будет инверсий, а последовательность в порядке убывания содержит инверсий (каждые два элемента образуют инверсию).
Решая задачу «Количество инверсий», примитивный алгоритм просматривает все возможные пары , что требует времени выполнения . Чтобы решить эту задачу за время с помощью алгоритма «разделяй и властвуй», мы разделяем вводный массив на две половины и делаем рекурсивный вызов обоих из них. Остаётся только вычислить количество инверсий, которые образованы двумя элементами из разных частей. Если делать это примитивным образом, то мы снова придём к времени выполнения , так как общее количество таких пар составляет . Оказывается, что если обе части уже отсортированы, количество инверсий из элементов разных половин можно вычислить за время . Это подсказывает нам, что вместо решения изначальной задачи, нам стоит решить более общую: вычислить количество инверсий в заданном массиве и в то же время отсортировать его.
✒️ Упражнение:
Измените алгоритм MergeSort для решения этой задачи.
- Формат ввода: Первая строка содержит целое число , следующая — последовательность целых чисел .
- Формат вывода: Количество инверсий в последовательности.
- Ограничения: , для всех .
Пример:
|
Ввод |
Вывод |
|
5 |
2 |
-
В примере две инверсии: () и
(). -
Совет: используйте полуоткрытые интервалы для рекурсивных реализаций
Решение
Попробуем использовать самый распространённый подход к методу «разделяй и властвуй»: разделим вводную последовательность на две половины, LeftHalf и RightHalf, и выполним рекурсивный вызов для каждой. Это позволит нам вычислить все инверсии, находящиеся в одной и той же половине. Однако это не подскажет нам количество разделённых инверсий, то есть количество пар , при которых находится в левой половине, находится в правой, а .
💡 Остановитесь и подумайте:
Возьмём элемент в . Каково количество разделённых инверсий, в которые входит ?
Даны массив и целое число . Пусть будет количеством элементов , которые меньше . Так как ответ на вопрос выше — это , наша задача заключается в том, чтобы быстро вычислить . Таким образом, мы приходим к следующей задаче: имея последовательность целых чисел и целое число , нам нужно найти в количество элементов, которые меньше . В случае неотсортированного массива это можно сделать за время , так как необходимо проверить каждый элемент массива. В варианте же отсортированного за время , если использовать двоичный поиск.
✒️ Упражнение:
Продемонстрируйте, как реализовать метод CountSmaller(List, x) для подсчёта количества элементов со значением меньше за время .
Так мы приходим к следующему алгоритму «разделяй и властвуй».
1CountInversions(List):
2 if ∣List∣ <= 1:
3 return 0
4 inversions = 0
5 // в случае нечётной длины
6 // центральный элемент может быть и слева, и справа
7 LeftHalf = левая половина List
8 RightHalf = правая половина List
9 inversions = inversions + CountInversions(LeftHalf)
10 inversions = inversions + CountInversions(RightHalf)
11 sort(RightHalf) // необходимо для двоичного поиска
12 for x in LeftHalf:
13 inversions = inversions + CountSmaller(RightHalf,x)
14 return inversions
Время выполнения (где — длина ) удовлетворяет рекуррентному соотношению
Слагаемое включает в себя два шага: сортировку и ответ на запросов CountSmaller. Эту рекуррентное соотношение нельзя напрямую вставить в основную теорему о рекуррентных соотношениях, так как элемент не имеет форму при константе . Однако мы можем проанализировать её таким же образом: рекурсивное дерево содержит уровней, общий размер всех задач на каждом уровне равен , а общее затраченное время на каждом уровне составляет . В итоге общее время выполнения составляет . Вместо того, чтобы формально это доказывать, мы улучшим вышеприведённый алгоритм так, чтобы он затрачивал время .
Можно быстро найти все разделённые инверсии, если наряду с подсчётом инверсий сортировать входную последовательность. То есть можно предположить, что алгоритм CountInversionsAndSort(List) возвращает количество инверсий в и сортирует . После двух рекурсивных вызовов обе половины отсортированы. На данном этапе нам нужно сделать две вещи: отсортировать всю последовательность и вычислить количество разделённых инверсий. Мы уже знаем, как достичь первой цели: этим занимается процедура . Это выглядит следующим образом.Пусть и будут первыми элементами отсортированных последовательностей и . Далее выбирается самый маленький из них и перемещается в увеличивающийся отсортированный список.
💡 Остановитесь и подумайте:
Можете ли вы найти количество разделённых инверсий, которые образует перемещаемый элемент?
Рассмотрим два случая.
- . В этом случае не больше каждого элемента , и поэтому не образует разделённых инверсий.
- . В этом случае меньше всех элементов , и поэтому образует разделённую инверсию с каждым из них.
Это приводит нас к следующему расширению метода Merge.
1Merge(LeftHalf, RightHalf):
2 SortedList = empty list
3 inversions = 0
4 while both LeftHalf and RightHalf are non-empty:
5 l = первый элемент LeftHalf
6 r = первый элемент RightHalf
7 if l <= r:
8 переместить l в SortedList
9 l = следующий элемент в LeftHalf
10 else:
11 переместить r в SortedList
12 r = следующий элемент в RightHalf
13 // учитываются только не перемещенные элементы
14 inversions = inversions + ∣LeftHalf∣
15 добавить все оставшиеся элементы LeftHalf и RightHalf в SortedList
16 return SortedList, inversions
И окончательная версия алгоритма CountInversions.
1CountInversions(List):
2 // список List будет отсортирован
3 if ∣List∣ <= 1:
4 return 0
5 LeftHalf = левая половина List
6 RightHalf = правая половина List
7 leftInv = CountInversions(LeftHalf)
8 rightInv = CountInversions(RightHalf)
9 List, splitInv = Merge(LeftHalf, RightHalf)
10 return leftInv + rightInv + splitInv