http://yangchuanhuahpu.blog.163.com/blog/static/186318840201242291838887/
给我们一个序列, 让我们求其逆序数:
如3 2 1 4
逆序数为: 2+1+0+0=3
我们这样定义一个序列的逆序数: 序列a1 a2 a3 a2 ...an
这个序列的逆序数C, 等于a1,a2...的逆序数的和.即 C=sum(Ci)
Ci为满足ai > aj (j > i)的数的总的个数, 即Ci = sum(ai > aj) (j >i).
我们一般写的算法一般会做N(N-1)/2次比较, 时间复杂度为: O(N^2).
下面采用的分而治之的思想来改进:
假设我们将序列a1 a2 a3 a2 ...an分成两份: B0=(a1 a2 an/......
阅读全文