Я пытаюсь подсчитать инверсию в массиве (два элемента a[i] и a[j] образуют инверсию, если a[i] > a[j] и i ‹ j). Я знаю, что эти проблемы легко решить с помощью грубой силы за O(n^2) и с помощью функции «Разделяй и властвуй» за O(nlgn).
Мой вопрос заключался в том, можно ли использовать метод группирования для достижения эффективности O (n) со знанием данных. Например, я уже знаю, что массив представляет собой перестановку 1-32 , поэтому максимальное количество элементов равно 32 (что означает, что мы можем что-то делать с группировкой).
Я думал об этом и заметил, что если мы вставляем элемент в ведро, то сумма всех ведер, превышающих его на момент вставки, является его счетчиком инверсии. Но если мы будем добавлять количество элементов в каждом сегменте каждый раз, это приведет к потере эффективности O(n). Любые предложения о том, как вести подсчет, чтобы снять этот штраф.
Обратите внимание, что перестановка может быть любой длины, но во время выполнения мы знаем количество элементов в перестановке. Таким образом, значение «n» известно во время выполнения, и перестановка состоит из элементов от «1» до «n».
Сортировка. Этот набор данных можно отсортировать с временной сложностью O(n), так как мы можем создать 32 корзины, и мы знаем, что в каждой корзине будет ровно один элемент. Таким образом, эффективность сортировки ведра, которая составляет O (n + M), составляет O (n + 1) = O (n) для этого конкретного примера.
