1. 问题描述

用改进后的分治算法来实现逆序对数问题，使其时间复杂度为 nlogn。
（逆序对数的定义：在数
组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对）。

2. 问题分析

2.1 改进前的方法

把数组中间分割成子数组，统计出子数组内部逆序对的数目，再统计出两个相邻子数组之间逆序对的数目。按照这种思路，可以写出下列伪代码：

// An highlighted block
def count _ Inv _ DC _1( A ) :
	# 统 计 左 边 的 子 数 组 逆 序 对 的 个 数
	a = count _ Inv _ DC _1( LA )
	# 统 计 右 边 的 子 数 组 逆 序 对 的 个 数
	b = count _ Inv _ DC _1( RA )
	# 统 计 两 个 相 邻 子 数 组 之 间 逆 序 对 的 个 数
	c = cross ( LA , RA )
return a + b + c

用传统的逻辑来实现 cross 函数，对左右子数组之间的每一个元素进行比较，需要 O(n^2) 的时间复杂度。那么，
T(n) = 2T(n / 2) + cn^2
由 Master Method 可知，该算法的时间复杂度为 O(n2
), 说明在这种情况下分治算法也无法提高效率。

2.2 改进后的方法

改进思路：在统计逆序对的过程中，对数组进行排序，使 cn2 → cn。

在合并时，每一层的比较次数是 n，一共有 logn 层，由此可得，该排序的时间复杂度是 O（nlogn）。
在做合并的时候将有序的特征进行传递，因此得到了性能的提升。

3. 实验代码

// An highlighted block
import time
import random
import matplotlib . pyplot as plt
import numpy as np
from scipy . optimize import curve _ fit

# 自 定 义 函 数 e 指 数 形 式
def func (x , a , b , c ) :
	return a * np . sqrt ( x ) *( b * np . square ( x ) + c )
	
def random _ list ( length ) :
	randomlist = []
	for i in range ( length ) :
		randomlist . append ( i +1)
	random . shuffle ( randomlist )
	return randomlist

def count _ Inv _ DC ( A ) :
	if len ( A ) <= 1:
		return A ,0
	else :
		mid = len ( A ) //2
		LA = A [: mid ]
		RA = A [ mid :]
		SLA , count 1 = count _ Inv _ DC ( LA ) # 统 计 左 边 的 子 数 组 逆 序 对 的 个 数
		SRA , count 2 = count _ Inv _ DC ( RA ) # 统 计 右 边 的 子 数 组 逆 序 对 的 个 数
		SA , count 3 = cross ( SLA , SRA ) # 统 计 两 个 相 邻 子 数 组 之 间 逆 序 对 的 个 数
	return SA , count 1+ count 2+ count 3

def cross ( LA , RA ) :
	# 边 排 序 边 计 数
	result = []
	i =0
	j =0
	count = 0
	while i < len ( LA ) and j < len ( RA ) :
		if LA [ i ] < RA [ j ]:
			result . append ( LA [ i ])
			i = i + 1
		else :
			result . append ( RA [ j ])
			count = len ( LA ) - i
			j = j + 1
	while i < len ( LA ) :
		result . append ( LA [ i ])
		i = i + 1
	while j < len ( RA ) :
		result . append ( RA [ j ])
		j = j + 1
	return result , count

if __ name __ == "__ main __":
	x = [100 ,1000 ,10000 ,100000 ,1000000]
	time _ list = []
	for index in range ( len ( x ) ) :
		average _ time = []
		
	for i in range (10) :
		# print ( ’ x : ’ , x [ index ])
		randomlist = random _ list ( x [ index ])
		# randomlist = random _ int _ list (1 , x [ index ] , x [ index ])
		total _ time = 0
		time _ start = time . time ()
		count _ Inv _ DC ( randomlist )
		time _ end = time . time ()
		total _ time = time _ end - time _ start
		average _ time . append ( total _ time )
	# 求 平 均 值
	average = np . mean ( average _ time )
	time _ list . append ( average )
print ( time _ list )

# 用 matplotlib 画 图
# plt . figure ()
# plt . plot (x , time _ list , marker = ’* ’ , label = " merge sort ")
# plt . show ()

# 定 义 x 、 y 散 点 坐 标
x = np . array ( x )
num = time _ list
y = np . array ( num )

# 非 线 性 最 小 二 乘 法 拟 合
popt , pcov = curve _ fit ( func , x , y )
# 获 取 popt 里 面 是 拟 合 系 数
print ( popt )
a = popt [0]
b = popt [1]
c = popt [2]
yvals = func (x ,a ,b , c ) # 拟 合 y 值

# 绘 图
plot 1 = plt . plot (x , y , ’s ’ , label = ’ original values ’)
plot 2 = plt . plot (x , yvals , ’r ’ , label = ’ polyfit values ’)
plt . xlabel ( ’x ’)
plt . ylabel ( ’y ’)
plt . legend ( loc =4) # 指 定 legend 的 位 置 右 下 角
plt . title ( ’ Inversions ’)
plt . show ()

# 统 计 100 个 随 机 数 中 逆 序 对 的 个 数
AList = random _ list (100)
countNum = count _ Inv _ DC ( randomlist )
print ("100 个 随 机 数 中 逆 序 对 数 的 个 数 为 ： " , countNum [1])

4. 实验结果

4.1 时间复杂度结论

计算不同范围大小下的随机数组中寻找逆序对数的个数所要消耗的时间，在多次实验求平均值，并对图像进行拟合处理后，得到上述图像。可以看到，该方法求解逆序对数问题的时间复杂度图像近似于 nlogn，这与我们理论验证的结果相同。

4.2 逆序对个数结论

随机生成 100 个数，实验得在该数组中存在 86 个逆序对。

参考和致谢

【1】逆序对数问题https://blog.csdn.net/contr4l_/article/details/80611675