1 3 ...(2n-1)2 4 ...2n求其逆序数?
问题描述:
1 3 ...(2n-1)2 4 ...2n求其逆序数?
答
选择1,2,3,┅,2n为正序,则1 3 ...(2n-1)2 4 ...2n,从2 开始有逆序数,个数为(2n-1-3)/2+1 =n-1个,4的有(2n-1-5)/2+1 =n-2个,直到2n-2有1个,2n没有.
总个数即为求等差数列(n-1)+(n-2)+ ┅ +1的和,为n(n-1)/2.