算法设计练习题——分治法(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)构成一个