Разработка и анализ алгоритма

Как проще всего посчитать инверсии? Разумеется, можно проверить каждую пару чисел (а,, а) и определить, образуют ли они инверсию; проверка займет время O(n2).

Сейчас мы покажем, как подсчитать инверсии намного быстрее, за время O(n log n).

Так как возможно квадратичное количество инверсий, такой алгоритм должен быть способен подсчитать инверсии без проверки отдельных инверсий. Общая идея состоит в применении стратегии (f) из раздела 5.1. Мы назначаем tп = \п!l\ и делим список на две части: a{, ..., am и am+l, ..., an. Сначала количество инверсий подсчитывается в каждой половине по отдельности, а затем считаются инверсии (а,, а) для двух чисел, принадлежащих разным половинам; хитрость в том, что это нужно сделать за время O(n), если мы хотим применить (5.2). Обра- тите внимание: инверсии «первая половина/вторая половина» имеют очень удоб- ную форму: они представляют собой пары (а,, аj), в которых а. находится в первой половине, аj находится во второй половине и аi > аj.

Чтобы упростить подсчет инверсий между половинами, мы заставим алгоритм также рекурсивно сортировать числа в двух половинах. Некоторое возрастание объема работы на шаге рекурсии (сортировка и подсчет инверсий) упростит «объ- единяющую» часть алгоритма.

Итак, главной частью процесса станет процедура «слияния с подсчетом». Предположим, мы рекурсивно отсортировали первую и вторую половины списка и подсчитали инверсии в каждой половине. Теперь имеются два отсортированных списка A и B, содержащих первую и вторую половины соответственно. Мы хотим объединить их с построением одного отсортированного списка C, одновременно подсчитав пары (a, b), у которых a A, b B, и a > b. По приведенному выше

определению это именно то, что необходимо для «объединяющего» шага, вычис- ляющего количество инверсий между половинами.

Эта задача тесно связана с более простой задачей из главы 2, в которой был сформирован соответствующий «объединяющий» шаг для сортировки слиянием: тогда у нас были два отсортированных списка A и B, которые нужно было объеди- нить в один отсортированный список за время O(n). На этот раз нужно сделать кое- что еще: не только построить один отсортированный список из A и B, но и подсчи- тать количество «инвертированных пар» (a, b), для которых a A, b B, и a > b.

Как выясняется, это делается практически так же, как для слияния. Процеду- ра «слияния с подсчетом» проходит по отсортированным спискам A и B, удаляя элементы от начала и присоединяя их к отсортированному списку C. На каждом конкретном шаге для каждого списка доступен указатель Current, обозначающий текущую позицию. Предположим, эти указатели в настоящее время указывают на элементы a. и b.. За один шаг мы сравниваем элементы a. и b., удаляем меньший элемент из списка и присоединяем его в конец списка C.

Со слиянием понятно, но как подсчитать количество инверсий? Так как списки A и B отсортированы, отслеживать количество обнаруженных инверсий на самом деле очень просто.

Каждый раз, когда элемент a. добавляется к C, новые инверсии не возникают, так как a. меньше всех элементов, оставшихся в списке B, и дол- жен предшествовать им всем. С другой стороны, если элемент b. присоединяется к списку C, значит, он меньше всех оставшихся элементов A и должен следовать после них всех, поэтому счетчик инверсий увеличивается на количество элементов, оставшихся в A. Это центральная идея алгоритма: за постоянное время учитыва- ется потенциально высокое количество инверсий. Процесс проиллюстрирован на рис. 5.5.

Рис. 5.5. Слияние двух отсортированных списков с одновременным подсчетом инверсий между ними


Ниже приведено описание алгоритма на псевдокоде.

Merge-and-Count (A,B)

Хранить для каждого списка указатель Current, инициализируемый указателем на начальный элемент

Хранить количество инверсий в переменной Count, инициализируемой 0

Пока оба списка не пусты:

Пусть a и b. - элементы, на которые указывают указатели Current Присоединить меньший из них к выходному списку Если меньшим является элемент b, то

Увеличить Count на количество элементов, оставшихся в A Конец Если

Переместить указатель Current в списке, из которого был выбран меньший элемент.

Конец Пока

Когда один из списков опустеет, присоединить остаток другого списка к выходному списку

Вернуть Count и объединенный список

Время выполнения алгоритма слияния с подсчетом может быть ограничено аргументом, аналогичным тому, который использовался для исходного алгоритма слияния в сортировке слиянием: каждая итерация цикла выполняется за посто- янное время, и при каждой итерации в выходной список добавляется элемент, который исключается из рассмотрения. Следовательно, количество итераций не может превышать сумму исходных длин A и B, а значит, общее время выполнения составляет O(n).

Процедура используется в рекурсивном алгоритме, который одновременно сортирует и подсчитывает количество инверсий в списке L.

Sort-and-Count (L)

Если список содержит один элемент, инверсий нет

Иначе

Разделить список на две половины:

A содержит первые n/2 элементов B содержит остальные n/2 элементов (rA, A) = Sort-and-Count(A)

(rB, B) = Sort-and-Count(B)

(r, L) = Merge-and-Count(A, B)

Конец Если

Вернуть r = rA + rB + r и отсортированный список L

Так как слияние с подсчетом выполняется за время O(n), время выполнения T(n) полной процедуры сортировки с подсчетом удовлетворяет рекуррентному отношению (5.1). Из (5.2) следует (5.7).

(5.7) Алгоритм сортировки с подсчетом i правильно сортирует входной список и подсчитывает количество инверсий; для списка с n элементами он выполняется за время O(n log n).

5.4.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Разработка и анализ алгоритма:

  1. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  2. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  3. § 2.ФУНКЦИИ МЕТОДОЛОГИИ В РАЗРАБОТКЕ МЕТОДИК АНАЛИЗА СОЦИАЛЬНЫХ ФАКТОВ
  4. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  5. АЛГОРИТМ
  6. АЛГОРИТМ УДАЧИ
  7. Алгоритм исцеления:
  8. Алгоритм избавления от боли
  9. 2. Специфика и алгоритмы работы с источниками.
  10. Алгоритм обработки результатов.
  11. СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
  12. Э. ТАНЕНБАУМ, А. ВУДХАЛЛ. ОПЕРАЦИОННЫЕ СИСТЕМЫ Разработка и реализация 3-е издание, 2007
  13. 2.7. Разработка анкеты
  14. Разработка Плана
  15. 6. Разработка перспектив
  16. Разработка и принятие Основного закона
  17. Состояние научной разработки проблемы.
  18. Правило разработки веера версий
  19. Правило разработки графических схем