逆序数怎么算
在Internet上的搜索引擎经常需要对信息进行比较。例如,可以通过某个人对一些事物的排名来估计他(或她)对各种不同信息的兴趣,从而实现个性化的服务。对于不同的排名结果可以用逆序来评价它们之间的差异。考虑1,2,…,n的排列i1,i2,...,in,如果其中存在ij,ik,使得j<k但是ij>ik,那么就称(ij,ik)是这个排列的一个逆序。一个排列含有逆序的个数称为这个排列的逆序数。例如,排列263451含有8个逆序(2,1),(6,3),(6,4),(6,5),(6,1),(3,1),(4,1),(5,1),它的逆序数就是8。显然,由1,2,…,n构成的所有n!个排列中,最小的逆序数是0,对应的排列就是12…n;最大的逆序数是n(n-1)/2,对应的排列就是n(n-1)…21。逆序数越大的排列与原始排列的差异度就越大。不难看到,如果使用顺序枚举逆序的蛮力算法来计算排列的逆序数,最坏情况下需要O(n2)的时间。利用二分归并排序算法Mergesort可以设计一个计数逆序的更好的算法,它仅使用O(nlog n)的时间。它的主要思想是:在递归调用算法分别对子数组L1与L2排序时,计数每个子数组内部的逆序;在归并排好序的子数组L1与L2的过程中,计数L1的元素与L2的元素之间产生的逆序。在算法运行中每次得到的逆序数都加到逆序总数上。下面是一个归并过程的例子。
假如两个排好序的子数组是1,4,5和2,3,6,在归并时,先比较1和2,1<2,没有逆序,移走1,第一个数组剩下2个数;接着比较4和2,4>2,第一个数组的4,5都与2构成逆序,即(4,2),(5,2),产生的逆序数恰好等于第一个数组剩下的元素个数。移走2,逆序总数加2。接着比较4和3,移走3,再增加2个逆序;接着比较4和6,移走4,不增加逆序;比较5和6,移走5,不增加逆序。在这个过程中逆序数共增加了4,恰好等于1,4,5与序列2,3,6的数之间构成的逆序总数。
(1)根据上面的描述写出算法的伪码。
(2)如果n是2的幂,计算算法使用的比较次数。