Вычисление количества "инверсий" в перестановке

Пусть A будет массивом размера N, мы называем пару индексов (i,j) "обратный", если i < j а также A[i] > A[j]

Мне нужно найти алгоритм, который получает массив размера N (с уникальными номерами) и вернуть количество инверсий во времени O(n*log(n)),

Источник

4 ответа

Решение

Вы можете использовать алгоритм сортировки слиянием.

В цикле алгоритма слияния левая и правая половины отсортированы по возрастанию, и мы хотим объединить их в один отсортированный массив. Обратите внимание, что все элементы с правой стороны имеют более высокие индексы, чем с левой стороны.

Предположим, что массив [leftIndex]> array [rightIndex]. Это означает, что все элементы в левой части, следующие за элементом с индексом leftIndex, также больше, чем текущий с правой стороны (потому что левая сторона отсортирована по возрастанию). Таким образом, текущий элемент в правой части генерирует инверсии numberOfElementsInTheLeftSide - leftIndex + 1, так что добавьте это в свой глобальный счетчик инверсий.

Как только алгоритм завершит выполнение, у вас есть ваш ответ, и сортировка слиянием будет O(n log n) в худшем случае.

Источник

Существует статья, опубликованная в SIAM в 2010 году Чамом и Патраску под названием " Подсчет инверсий, автономный подсчет ортогонального диапазона и связанные с этим проблемы", в котором описывается алгоритм, занимающий время O(n sqrt(log(n))). В настоящее время это самый известный алгоритм, и он улучшает старый алгоритм O(n log(n) / log(log(n))). Из аннотации:

Мы даем алгоритм времени O(n sqrt(lg n)) для подсчета количества инверсий в перестановке на n элементах. Это улучшает давнюю предыдущую границу O(n lg n / lg lg n), которая вытекает из структуры данных Дитца [WADS'89], и отвечает на вопрос Андерссона и Петерссона [SODA'95]. Поскольку результат Дитца, как известно, является оптимальным для соответствующей задачи динамического ранга, наш результат демонстрирует значительное улучшение в автономном режиме.

Наша новая техника довольно проста: мы выполняем "вертикальное разбиение" дерева (сродни деревьям Ван Эмде Боаса) и используем идеи из внешней памяти. Однако методика находит многочисленные применения: например, мы получаем

  • в d измерениях - алгоритм для ответа на n автономных запросов подсчета ортогональных диапазонов за время O (n lgd-2 + 1 / d n);
  • улучшенное время построения онлайновых структур данных для подсчета ортогонального диапазона;
  • улучшенное время обновления для проблемы частичных сумм;
  • более быстрые алгоритмы Word RAM для определения максимальной глубины в расположении выровненных по оси прямоугольников и для задачи выбора наклона.

В качестве бонуса мы также даем простой (1 + ε)-приближенный алгоритм для подсчета инверсий, который выполняется за линейное время, улучшая предыдущий O(n lg lg n), ограниченный Андерссоном и Петерссоном.

Источник

Я думаю, что лучший способ сделать это (и это только потому, что мне нравится структура данных) - это использовать двоичное индексированное дерево. Имейте в виду, что если все, что вам нужно, это решение, сортировка слиянием будет работать так же хорошо (я просто думаю, что эта концепция совершенно потрясающая!). Основная идея заключается в следующем: создать структуру данных, которая обновляет значения в O(log n) и отвечает на запрос "Сколько чисел меньше x уже есть в массиве до сих пор?" Учитывая это, вы можете легко ответить, сколько из них больше, чем х, что способствует инверсии с х в качестве второго числа в паре. Например, рассмотрим список {3, 4, 1, 2}.

При обработке 3 других чисел пока нет, поэтому инверсии с 3 на правой стороне = 0 При обработке 4 число чисел, меньших 4, пока = 1, таким образом, число больших чисел (и, следовательно, инверсий) = 0. при обработке 1 число чисел меньше 1 = 0, это число больших чисел = 2, что способствует двум инверсиям (3,1) и (4,1). Та же логика применима к 2, который находит 1 число меньше его и, следовательно, 2 больше его.

Теперь единственный вопрос - понять, как эти обновления и запросы происходят в журнале n. Упомянутый выше URL является одним из лучших учебных пособий, которые я читал по этому вопросу.

Источник

Это оригинальные алгоритмы MERGE и MERGE-SORT от Cormen, Leiserson, Rivest, Stein. Введение в алгоритмы:

MERGE(A,p,q,r)
 1  n1 = q - p + 1
 2  n2 = r - q
 3  let L[1..n1 + 1] and R[1..n2 + 1] be new arrays
 4  for i = 1 to n1
 5      L[i] = A[p + i - 1]
 6  for j = 1 to n2
 7      R[j] = A[q + j]
 8  L[n1 + 1] = infinity
 9  R[n2 + 1] = infinity
10  i = 1
11  j = 1
12  for k = p to r
13      if L[i] <= R[j] 
14          A[k] = L[i]
15          i = i + 1
16      else A[k] = R[j]
17          j = j + 1

а также

MERGE-SORT(A,p,r)
 1 if p < r
 2     q = floor((p + r)/2)
 3     MERGE-SORT(A,p,q)
 4     MERGE-SORT(A,q + 1,r)
 5     MERGE(A,p,q,r)

в строках 8 и 9 в бесконечности MERGE находится так называемая сторожевая карта, которая имеет такое значение, что все элементы массива меньше ее. Чтобы получить число инверсии, можно ввести глобальный счетчик, скажем, ninv, инициализированный в ноль перед вызовом MERGE-SORT, а затем модифицировать алгоритм MERGE, добавив одну строку в операторе else после строки 16, что-то вроде

ninv += n1 - i

чем после того, как MERGE-SORT закончится, ninv будет держать количество инверсий

Источник
Другие вопросы по тегам