вопрос по инверсии

Question

Я прочитал что-то на сайте, что означает инверсия, если i<j, то A[i]>A[j], и у него есть некоторые упражнения по этому поводу, у меня много вопросов, но я сначала хочу задать только один из них, а затемвыполняй другие упражнения сам, если смогу !!

Упражнение: Какой массив перестановок (1,2, ..., n) имеет наибольшее число инверсий?Что это? спасибо

Answer 1

Очевидно, N, ..., 2, 1 имеет наибольшее количество инверсий. Каждая пара - это инверсия. Например, для N = 6 у нас есть 6 5 4 3 2 1. Инверсии 6-5, 6-4, 6-3, 6-2, 6-1, 5-4, 5-3 и так далее. Их число N * (N - 1) / 2.

Answer 2

Я никогда не слышал термин инверсия , используемый таким образом.

Уменьшающийся массив длины N для N> 0 имеет 1/2 * N * (N-1) пары яА [J].Это максимально возможное.

Answer 3

Ну, тождественная перестановка (1,2, ..., n) не имеет инверсий. Поскольку инверсия - это пара элементов, которые находятся в обратном порядке, чем их индексы, ответ, вероятно, предполагает некоторое изменение этой перестановки.