Поиск единомышленников
Очередная разминка с лёгким превышением заявленного срока.
Задача: найти количество инверсий в перестановке.
Дан массив чисел от 1 до n в случайном порядке. Числа не повторяются. Найти число инверсий в этом массиве. Инверсия - это пара чисел, стоящих в убывающем порядке, когда большее предшествует меньшему. Обращаю внимание, что пара чисел, не обязательно стоящих в массиве подряд. То есть, если к упорядоченному массиву дописать в начало число, которое больше всех элементов массива, оно породоит n-1 инверсию.
Формальное определение: в массиве A инверсией считаем пару чисел i,j, где i < j, такие, что A[i] > A[j].
Соответственно, максимальное количество инверсий будет наблюдаться в массиве, отсортированном в обратном порядке, и это число n(n-1)/2.
Вот для затравки интересный графический алгоритм для поиска инверсий:
Мы располагаем исходный массив и сортированный рядом, соединяем одинаковые числа и количество пересечений - это количество инверсий, а сами пересения - это и есть инверсии.
Актуальность задачи: Кроме разминки, это можно использовать для определения количественной меры похожести двух списков. Например, приняв один из них за "правильный порядок", посчитать количество инверсий во втором, относительно первого. Это, в свою очередь, можно использовать для модной нынче штуки, под названием коллективная фильтрация - на основании похожести ваших оценок товаров, фильмов, книг оценкам других пользователей того или иного сервиса предлагать вам товары, фильмы, книги, которые выбрали "похожие" на вас люди.
Для удобства проверки вот вам одна перестановка с правильным ответом.
Очевидный, или наивный алгоритм, даёт O(n^2). На среднем компьютере - 40 минут для 100000 чисел.. Хорошие решения дают на том же объёме данных не превышают три секунды.
Задача со звёздочкой: как поведёт себя ваше решение, если это не перестановка, а массив случайных чисел, то есть, если в массиве есть дубликаты? Есть ли более эффективные решениия именно для массива без дубликатов, которые на массиве с повторяющимися числами не будут работать или деградируют до квадрата?
Удачи!