关于求逆序对问题的研究

一、问题介绍

逆序对数经常用来评判两个数组相似度高低，其在很多评分网站得到了广泛的应用。假如你对五部电影进行打分，你的打分分别为[1,2,4,3,5],其中评者A的打分分别为[2,4,1,3,5],评者B的打分分别为[3,4,1,5,2]，那么在推荐评者或者评者的文章时，应该把评者A推荐给你还是评者B呢？应该是评者A。这其中就涉及到了求逆序对数问题，那么什么是逆序对数呢。对于一个输入序列，假如元素的索引$i<j$且元素$a_{i}>a_{j}$，那么$a_{i}$与$a_{j}$就是一对逆序对，该序列中所有逆序对的总数就是逆序对数。在上述的评分中，你的打分的序列的逆序对数为1，评者A评分的序列的逆序对数为2，评者B评分的序列的逆序对数为3，你的打分的逆序对数与评者A更为接近，所以将评者A推荐给你。那么假如给你一个序列，你要如何求出该序列的逆序对数以及其所有的逆序对呢。

二、算法设计

一个很简单的求解方式就是遍历该数组中的所有元素，判断在该元素右边的值是否比该元素小，如果比该元素小，这两个数就构成了逆序对。通过分析，很容易发现这种解法的时间复杂度为$O(n^{2})$，那么有没有更高效的求解方式呢？

我发现该问题可以分解为更短序列的子问题，这不禁让我想要尝试使用分治算法求解该问题。那么首先我们将其分解为子问题，假定输入序列为A，将输入序列分为两个部分，左边的为LA，右边的为RA，那么可以发现，A与LA、RA只是序列元素数量的不同，求解A的逆序对与逆序对数的策略同样适用于LA与RA，那么剩下的问题就是如何求解与合并这些子问题。可以发现对于A的逆序对数等于LA的逆序对数加上RA的逆序对数再加上跨界情况下的逆序对数，所谓跨界情况就是指LA中的某一元素可能与RA中的某一元素构成逆序对。

此时该问题的核心就变成了如何求跨界情况下的逆序对。假如每次归并都将AL中的元素与RA中的元素逐个比较，那么不难得出跨界情况下的时间复杂度为$O(n^{2})$，根据主方法可以发现此时使用分治算法的时间复杂度仍为 $O(n^{2})$。那么该如何处理跨界情况下的求解方式可以提高算法的时间复杂度呢？

经过不断的分析与尝试，我将序列排序减少了跨界情况下的比较次数。假设LA与RA都是经过排序的列表，那我们分别从LA与RA取出一个元素$a_{i}$与$b_{j}$，如果$a_{i}<b_{j}$，那么我们取$a_{i+1}$与$b_{j}$比较，但如果$a_{i}>b_{j}$，那么可以得到 $a_{i}$以及LA中下标大于i的元素都与$b_{j}$构成逆序对数，之后我们就只需要继续比较$a_{i}$与$b_{j+1}$。但此时又有一个问题，就是排序会影响序列中的元素的顺序，会影响我们得到的逆序对数。那么此时我们就需要边排序边记录逆序对数。接下来的代码实现与归并排序十分相似，不过是在排序的过程中记录了逆序对。

三、算法实现

def find_inversion(A,inv_list):
    lenA = len(A)
    if lenA <= 1:
        return 0,A
    mid = lenA//2
    LA = A[:mid]
    RA = A[mid:]
    countLA,LA = find_inversion(LA,inv_list)
    countRA,RA = find_inversion(RA,inv_list)
    countLRA,mergedA = merge_inversion(LA,RA,inv_list)
    
    return countLA+countRA+countLRA,mergedA

def merge_inversion(LA,RA,inv_list):
    i,j,inv_count = 0,0,0
    alist=[]
    lenLA = len(LA)
    lenRA = len(RA)
    while i<lenLA and j<lenRA:
        if LA[i]<RA[j]:
            alist.append(LA[i])
            i+=1
        else:
            inv_count += lenLA-i
            for index in range(i,lenLA):
                inv_list.append([RA[j],LA[index]])
            alist.append(RA[j])
            j+=1
    while i<lenLA:
        alist.append(LA[i])
        i+=1
    while j<lenRA:
        alist.append(RA[j])
        j+=1
    return inv_count,alist

inv_list=[]
A=[8,1,4,2,3]
inv_count,sorted_list=find_inversion(A,inv_list)
print("逆序对数量为{}，逆序对分别是{}".format(inv_count,inv_list))

我定义了两个函数，分别为find_inversion与merge_inversion,对应的是分解子问题与归并。其中的find_inversion的输入参数inv_list用来记录结果，A为需要求解的序列。在父函数find_inversion中将父序列分解为两个子序列LA与RA传入子函数find_inversion中进行递归操作，最后使用merge_inversion进行归并操作。在merge_inversion中边排序边记录逆序对与逆序对数。通过观察可以发现merge_inversion可以发现merge_inversion中有三个循环，三个循环的时间复杂度均为$O(n)$，那么merge_inversion的时间复杂度为$O(n)$，也就是分治算法中的f(n)为$O(n)$。因此我可以得到以下的公式:

$T(n) = 2T(\frac{n}{2})+O(n)$

根据主方法，我们易得使用分治算法求解逆序对问题的时间复杂度为$O(nlogn)$。

四、结论

我研究并解决了逆序对问题，从最容易想到的两层遍历的穷举法，到想到使用分治算法进行求解，再到优化分治算法求解该问题的方式，最终我解决了这个问题，并将时间复杂度优化到了$O(nlogn)$。经过该问题的研究，我们可以发现对于可以分解为小问题的问题，我们使用分治算法常常能够简化该问题并且优化该问题的时间复杂度，同时对于优化比较的过程，排序常常能起到很好的效果。