Пусть A[1...n] представляет собой массив, состоящий из n разных чисел.Вычислить количество инверсий
Пара (i, j) называется обратный, если i < j and A [i] > A [j].
Пример:
А: = (2, 3, 8, 6, 1) => А имеет 5 инверсий.
Задача:
запись программа, чтобы найти число инверсий в массиве А [1..n], такой, что сложность алгоритма O (N * LogN).
Эта проблема может быть решена на основе сортировки слияния.
строго говоря, вы должны изменить процедуру merge(A, B), чтобы она возвращала количество пар (a, b) such that a in A, b in B and b > c.
Как вы можете видеть время работы, которое требуется, чтобы решить эту проблему, является время работы от сортировки слиянием, следовательно O(n * log(n))
Я пробовал, но это неправда. Вы можете мне помочь Код –
Не могли бы вы разместить свой код, чтобы я мог провести вас по пути к решению –
Добро пожаловать на переполнение стека! Домашние вопросы должны показывать усилие и текущий код, который у вас есть. Вы вряд ли получите хороший ответ, сбрасывая ваш вопрос о домашнем задании дословно; объясните, с чем вы боретесь, и предоставите четкую отладочную информацию. – Aurora0001
http://stackoverflow.com/a/40001355/1040597 – Tempux