7.4. Подсчёт инверсий

Количество инверсий в последовательности — показатель того, насколько последовательность отсортирована. Например, в неубывающей последовательности не будет инверсий, а последовательность в порядке убывания содержит инверсий (каждые два элемента образуют инверсию).

Решая задачу «Количество инверсий», примитивный алгоритм просматривает все возможные пары , что требует времени выполнения . Чтобы решить эту задачу за время с помощью алгоритма «разделяй и властвуй», мы разделяем вводный массив на две половины и делаем рекурсивный вызов обоих из них. Остаётся только вычислить количество инверсий, которые образованы двумя элементами из разных частей. Если делать это примитивным образом, то мы снова придём к времени выполнения , так как общее количество таких пар составляет . Оказывается, что если обе части уже отсортированы, количество инверсий из элементов разных половин можно вычислить за время . Это подсказывает нам, что вместо решения изначальной задачи, нам стоит решить более общую: вычислить количество инверсий в заданном массиве и в то же время отсортировать его.

✒️ Упражнение:
Измените алгоритм MergeSort для решения этой задачи.

• Формат ввода: Первая строка содержит целое число , следующая — последовательность целых чисел .
• Формат вывода: Количество инверсий в последовательности.
• Ограничения: , для всех .

Пример:

Ввод	Вывод
5 2 3 9 2 9	2

• В примере две инверсии: () и
  ().

• Совет: используйте полуоткрытые интервалы для рекурсивных реализаций

Решение

Попробуем использовать самый распространённый подход к методу «разделяй и властвуй»: разделим вводную последовательность на две половины, LeftHalf и RightHalf, и выполним рекурсивный вызов для каждой. Это позволит нам вычислить все инверсии, находящиеся в одной и той же половине. Однако это не подскажет нам количество разделённых инверсий, то есть количество пар , при которых находится в левой половине, находится в правой, а .

💡 Остановитесь и подумайте:
Возьмём элемент в . Каково количество разделённых инверсий, в которые входит ?

Даны массив и целое число . Пусть будет количеством элементов , которые меньше . Так как ответ на вопрос выше — это , наша задача заключается в том, чтобы быстро вычислить . Таким образом, мы приходим к следующей задаче: имея последовательность целых чисел и целое число , нам нужно найти в количество элементов, которые меньше . В случае неотсортированного массива это можно сделать за время , так как необходимо проверить каждый элемент массива. В варианте же отсортированного за время , если использовать двоичный поиск.

✒️ Упражнение:
Продемонстрируйте, как реализовать метод CountSmaller(List, x) для подсчёта количества элементов со значением меньше за время .

Так мы приходим к следующему алгоритму «разделяй и властвуй».

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

Время выполнения (где — длина ) удовлетворяет рекуррентному соотношению

Слагаемое включает в себя два шага: сортировку и ответ на запросов CountSmaller. Эту рекуррентное соотношение нельзя напрямую вставить в основную теорему о рекуррентных соотношениях, так как элемент не имеет форму при константе . Однако мы можем проанализировать её таким же образом: рекурсивное дерево содержит уровней, общий размер всех задач на каждом уровне равен , а общее затраченное время на каждом уровне составляет . В итоге общее время выполнения составляет . Вместо того, чтобы формально это доказывать, мы улучшим вышеприведённый алгоритм так, чтобы он затрачивал время .

Можно быстро найти все разделённые инверсии, если наряду с подсчётом инверсий сортировать входную последовательность. То есть можно предположить, что алгоритм CountInversionsAndSort(List) возвращает количество инверсий в и сортирует . После двух рекурсивных вызовов обе половины отсортированы. На данном этапе нам нужно сделать две вещи: отсортировать всю последовательность и вычислить количество разделённых инверсий. Мы уже знаем, как достичь первой цели: этим занимается процедура . Это выглядит следующим образом.Пусть и будут первыми элементами отсортированных последовательностей и . Далее выбирается самый маленький из них и перемещается в увеличивающийся отсортированный список.

💡 Остановитесь и подумайте:
Можете ли вы найти количество разделённых инверсий, которые образует перемещаемый элемент?

Рассмотрим два случая.

• . В этом случае не больше каждого элемента , и поэтому не образует разделённых инверсий.
• . В этом случае меньше всех элементов , и поэтому образует разделённую инверсию с каждым из них.

Это приводит нас к следующему расширению метода 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