вычисление числа «инверсий» в перестановке

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

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

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

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

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

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

    В 2010 году опубликована статья, опубликованная в SIAM в Cham и Patrascu под заголовком « Подсчет пересчета», «Одиночный ортогональный диапазон подсчета» и «Связанные проблемы», который дает алгоритм, определяющий время 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]. Как известно, результат Дица является оптимальным для связанной проблемы динамического ранжирования, наш результат демонстрирует значительное улучшение настройки в автономном режиме.

    Наша новая техника довольно проста: мы выполняем «вертикальное разбиение» trie (подобно деревьям Van Emde Boas) и используем идеи из внешней памяти. Тем не менее, техника находит множество приложений: например, мы получаем

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

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

    Я думаю, что это самый удивительный способ сделать это (и только потому, что мне нравится структура данных) – использовать двоичное индексированное дерево . Имейте в виду, если все, что вам нужно, это решение, слияние будет работать так же хорошо (я просто думаю, что это понятие полностью скалывает!). Основная идея заключается в следующем: Создайте структуру данных, которая обновляет значения в O (log n) и отвечает на запрос «Сколько чисел меньше x уже произошло в массиве до сих пор?» Учитывая это, вы можете легко ответить, сколько из них больше x, что способствует инверсии с 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 проведет количество инверсий

    Interesting Posts
    Давайте будем гением компьютера.