В этом параграфе вы познакомитесь с задачей на определение количества инверсий в массиве — то есть пар элементов, стоящих в неправильном порядке. Вы узнаете, как решать эту задачу не полным перебором, а гораздо быстрее — с помощью модифицированной сортировки слиянием. Этот подход поможет вам понять, как сочетать сортировку и вычисления в одном алгоритме.
Ключевые вопросы параграфа
- Что такое инверсии и как их находить?
- Почему перебор всех пар работает медленно и как это ускорить?
- Как работает алгоритм подсчёта инверсий на основе сортировки слиянием?
Количество инверсий в последовательности
Количество инверсий в последовательности — показатель того, насколько последовательность отсортирована. Например, в неубывающей последовательности не будет инверсий, а последовательность в порядке убывания содержит инверсий (каждые два элемента образуют инверсию).
Решая задачу «Количество инверсий», примитивный алгоритм просматривает все возможные пары , что требует времени выполнения . Чтобы решить эту задачу за время с помощью алгоритма «разделяй и властвуй», мы разделяем вводный массив на две половины и делаем рекурсивный вызов обоих из них. Остаётся только вычислить количество инверсий, которые образованы двумя элементами из разных частей.
Если делать это примитивным образом, то мы снова придём к времени выполнения , так как общее количество таких пар составляет . Оказывается, что если обе части уже отсортированы, количество инверсий из элементов разных половин можно вычислить за время .
Это подсказывает нам, что вместо решения изначальной задачи, нам стоит решить более общую: вычислить количество инверсий в заданном массиве и в то же время отсортировать его.
Упражнение
Измените алгоритм 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
Что дальше
Теперь вы умеете находить количество инверсий в массиве с помощью модифицированной сортировки. Вы увидели, как объединять рекурсивное деление с анализом данных и использовать «побочные эффекты» сортировки для аналитических целей.
Далее — последняя задача главы: вы узнаете, как найти пару ближайших точек на плоскости за , используя те же идеи — сортировку, деление и точный контроль над шагами объединения.
А пока вы не ушли дальше — закрепите материал на практике:
- Отметьте, что урок прочитан, при помощи кнопки ниже.
- Пройдите мини-квиз, чтобы проверить, насколько хорошо вы усвоили тему.
- Перейдите к задачам этого параграфа и потренируйтесь.
- Перед этим — загляните в короткий гайд о том, как работает система проверки.
Хотите обсудить, задать вопрос или не понимаете, почему код не работает? Мы всё предусмотрели — вступайте в сообщество Хендбука! Там студенты помогают друг другу разобраться.
Ключевые выводы параграфа
- Инверсии — это пары элементов в неправильном порядке: и .
- Полный перебор всех пар даёт сложность , но можно улучшить до , используя сортировку слиянием.
- Во время слияния двух отсортированных частей можно одновременно считать количество инверсий.
- Такой подход позволяет комбинировать сортировку и подсчёт статистик за одно и то же время.