题目

线性代数 求逆序数题
第一题：1,3……（2n-1）2,4……2n
第二题：1,3……(2n-1)2n(2n-2)……2

提问时间：2020-10-30

答案

第一题结果是n(n-1)/2
首先,前n个数都是从小到大排列的,没有逆序数对.
然后,看2,前面n个数除了1以外的n-1个数都比它大,每一个都与它组成一对逆序数对,就有n-1个；
接着,看4,前面n个数除了1和3以外的n-2个数都比它大,每一个都与它组成一对逆序数对,就有n-2个；
.
到了2n-2时,就只有2n-1比它大,有一个逆序数对.
2n 是0.
加起来就是 0+1+2+……（n-1）=n(n-1)/2
第二题结果是n(n-1)
首先,前n个数都是从小到大排列的,没有逆序数对.
然后,看2,前面2n-1个数除了1以外的2n-2个数都比它大,每一个都与它组成一对逆序数对,就有2n-2个；
接着,看4,前面2n-2个数除了1和3以外的2n-4个数都比它大,每一个都与它组成一对逆序数对,就有2n-4个；
.
到了2n-2时,有2个比它大,有2个逆序数对.
2n 是0.
加起来就是 2*【0+1+2+……（n-1）】=n(n-1)