算法实现算法实现逆序对问题(分支法)
Nuyoah 逆序对(分治法)
逆序对的含义
什么是逆序对?
例如上面这个表格第一行是数组序号,第二行是数组元素
当序号小的数组元素值大于序号大的数组元素值的时候称这两个数为逆序对
例如:
(4,3)(4,5)就是逆序对
枚举法
我们通过两层for循环来遍历这个数组,挨个寻找到所有的逆序对
分治法
我们把数组分为两个部分对每个部分分别求解,使用二分法,对每个部分分别求出最大子序列,然后再求出合并之后的最大子序列,最后让这三部分相加。
最后让这三个相加得出最后的逆序对个数
求解S3的方法:
-
使用枚举法,遍历前面的和后面的分别比较求解
但是最后的时间复杂度还是O(n2)
所以直接求解S3的分而治之和蛮力枚举并未提高算法运行时间
- 原因:我们每次在寻找A[i] 里面那个元素比A[j]的小的时候,都要遍历一遍A[i] ,这样时间比较多
- 改进方法:我们可以通过讲数组A[i] 和A[j]分别进行排序,然后使用二分查找进行查找对应元素,这样算法效率就能提高不少
-
排序之后使用二分法求解
分别对数组A[1…m]和A[m + 1…n]进行排序
对于每个A[j] e A[m+ 1…n],采用二分查找为其在A[1…m]中定位
A[j]在A[1…m]定位点右侧的元素均可与A[j]构成逆序对
求解S2 ;的算法运行时间:O(nlogn)
分治框架的算法运行时间:T(n) = 2T(n/2)+o(nlogn)
算法实例
先二分
后归并
时间复杂度分析
代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65
|
def reverse_order_pair(num_array, start, end): if start == end: return num_array[start:start+1], 0
mid = int((end-start)/2 + start)
re_left, num_left = reverse_order_pair(num_array, start, mid)
re_right, num_right = reverse_order_pair(num_array, mid+1, end) num_reverse = mid_reverse_num(re_left, re_right) return re_left, num_reverse + num_left + num_right
def mid_reverse_num(left_array, right_array): num_reverse = 0 left_num = 0 right_num = 0
while((left_num < len(left_array)) and (right_num < len(right_array))):
if left_array[left_num] > right_array[right_num]: num_reverse += (len(left_array) - left_num)
left_array.insert(left_num, right_array[right_num])
left_num += 1 right_num += 1 else: left_num += 1 if left_num == len(left_array): left_array.extend(right_array[right_num:len(right_array)]) elif right_num != len(right_array): num_reverse += (len(left_array)-left_num-1) return num_reverse
X = [13,8,10,6,15,18,12,20,9,14,17,19]
array, num = reverse_order_pair(X, 0, len(X)-1)
print(num) print(array)
|