算法设计练习题——分治法（2）

74 阅读 0 评论 49 点赞

我是靠谱客的博主任性眼睛，这篇文章主要介绍算法设计练习题——分治法（2），现在分享给大家，希望可以做个参考。

1 、设计一个“三路归并”的排序算法，并分析它的时间复杂性。

每3个一组，共n/3组，每组比较3次。
类比二路归并。
即3叉树倒过来。
	T（n） = 0    n==1
	T（n） = 1     n==2
	T（n） = 3    n ==3
	T（n） = 3T(n/3) + O(n) -------最后一层
	T(n) = O(nlogn)

2、逆序对数求解：有长度为N的浮点数组A，元素分别为a1, a2, …, aN。如果满足i<j且ai>aj，则(ai, aj)构成一个逆序对。设计分治方法求解数组A的逆序对个数，并分析算法的时间复杂性。

将数组分成两组，
前一半A[1:n/2]，后一半A[n/2+1:n]分别求逆序对；
然后找前一半和后一半组成的逆序对。
在每次找逆序对时，将元素大小排序，得到新的B[1:n/2]，C[1:n/2+1]
每次分别取前一半，后一半最小值B【1】，C【1】.
如果B【1】<C【1】,则前B【1】和后一半每个元素都能构成逆序对.取B中下一个数B【2】和C【1】接着比较；如果B【1】>C【1】，则取C的下一个数C【2】和B【1】进行比较，以此类推。
T（n）= O(1),n=1,2
T（n）= 	2T（n/2）+O(n)
T(n)=O(nlogn)