我在网站上读过一些东西，倒置意味着如果i<j那么A[i]>A[j]，它有一些关于这个的练习，我有很多问题，但我想一开始只问其中一个，然后如果可以的话，我会自己做其他练习！！
练习：哪个排列数组 (1,2, ..., n) 的反转次数最多？这些是什么？ 谢谢
问问题
167 次
3 回答
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。
于 2010-06-20T14:46:11.580 回答
0
好吧，恒等排列 (1,2,...,n) 没有反转。由于反转是一对与它们的索引相反的元素，答案可能涉及该排列的一些反转。
于 2010-06-20T14:45:26.717 回答
0
我从未听说过以这种方式使用的术语反转。
一个长度为 N 的递减数组，对于 N>0，有 1/2*N*(N-1) 对 i<j 和 A[i]>A[j]。这是最大可能的。
于 2010-06-20T14:46:11.520 回答