Я прочитал что-то на сайте, что инверсия означает, что i<j, то A[i]>A[j], и у него есть несколько упражнений об этом, у меня много вопросов, но сначала я хочу спросить только одного из них, а затем я сделаю другие упражнения, если я могу!вопрос об инверсии
Упражнение: Какой массив перестановок (1,2, ..., n) имеет наибольшее количество инверсий? Что это? спасибо
Ясно 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.
aha Я получаю это также благодаря вашей ссылке mathworld.wolfram.com/PermutationInversion.html – user355002
также это правильно, если массив больше в порядке его инверсии будет больше ??? – user355002
Больше в порядке не определенный срок. Но интуитивно перестановка, которая больше обращается вспять, вероятно, будет иметь больше инверсий, чем необратимая. Но опять же это зависит от перестановок, которые вы сравниваете. –
Ну, тождественная перестановка (1,2, ..., n) не имеет инверсий. Поскольку инверсия представляет собой пару элементов, которые находятся в обратном порядке, чем их индексы, ответ, вероятно, предполагает некоторое изменение этой перестановки.
Там идет мой тонкий намек ... – Amnon
Я никогда не слышал термин инверсия используется таким образом.
Уменьшающийся массив длины N при N> 0 имеет пары 1/2 * N * (N-1) i < j с A [i] > A [j]. Это максимально возможно.
http://mathworld.wolfram.com/PermutationInversion.html –
@Petar: Спасибо. Я думаю, что Кнут не использует этот термин. –
Основываясь на ваших предыдущих вопросах, я помечен как домашнее задание. Не стесняйтесь удалять его, если нет. Если это домашнее задание, я предлагаю вам оставить его, поскольку люди будут более полезны (по вашему пониманию предмета), если у вас есть какие-либо сомнения и т. Д. – 2010-06-20 14:44:18
это не моя домашняя работа, но мне нужны люди, чтобы быть более полезными, поэтому я сохранить этот тег :) – user355002