概述
求逆序对是大学本科学习算法阶段经常遇到的一个比较经典的题目，不过一直没有好好地去想过，最近在看算法导论时在课后练习题中又看到了这个题目，于是花了点时间写了一下。
逆序对的定义是：在一个序列A中，假设存在下标i，j， i < j， 且 Ai > Aj， 则称{Ai,Aj} 是一对逆序对。而求逆序对的题目则是给出一个序列，求这个序列中存在的逆序对数量（也可能是要求输出有哪些逆序对）。
初看到这个题目时，可能会想，从序列的第一个数开始，对于每一个数，遍历下标在其后的序列中的数，根据遍历的数和待判断的数的大小关系即可知道是否是逆序对。显然，该方法的时间复杂度是O（n^2）的。实际上是存在更为高效的算法的，我们发现，对于该题目，我们可以将序列分成子序列，并分别求解各个子序列中存在的逆序对数量，然后将结果合并，即可求出整个序列的逆序对，也就是采用分治法能更加高效地解决这个问题。
本题中分治法的细节如下：对于一个序列，将其分解成两个等大的子序列，称其为左序列和右序列，那么逆序对存在于如下三处：1.左序列中的逆序对&#
最后
以上就是粗心柚子为你收集整理的分治求逆序对算法的全部内容，希望文章能够帮你解决分治求逆序对算法所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复