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

Авторы: Алексей Толстиков, Александр Куликов

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

Ключевые вопросы статьи

• Что такое инверсии и как их находить?
• Почему перебор всех пар работает медленно и как это ускорить?
• Как работает алгоритм подсчёта инверсий на основе сортировки слиянием?

Количество инверсий в последовательностиКоличество инверсий в последовательности

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

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

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

Это подсказывает нам, что вместо решения изначальной задачи, нам стоит решить более общую: вычислить количество инверсий в заданном массиве и в то же время отсортировать его.

УпражнениеУпражнение

Измените алгоритм MergeSort для решения этой задачи.

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

ПримерПример

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

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

РешениеРешение

Попробуем использовать самый распространённый подход к методу «разделяй и властвуй»: разделим вводную последовательность на две половины, 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

Что дальшеЧто дальше

Теперь вы умеете находить количество инверсий в массиве с помощью модифицированной сортировки. Вы увидели, как объединять рекурсивное деление с анализом данных и использовать «побочные эффекты» сортировки для аналитических целей.

Далее — последняя задача раздела: вы узнаете, как найти пару ближайших точек на плоскости за , используя те же идеи — сортировку, деление и точный контроль над шагами объединения.

Ключевые выводы статьи

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