分治法是指将一个复杂的，规模为n的问题分解为k个规模较小的子问题，这些子问题相互独立且与原问题情势雷同，递归的解这些子问题，然后将各子问题的解归并得到原问题的解的算法筹划计谋。
对于无序序列a[low...high]，接纳分治法求最大元素max1和次大元素max2的过程如下：
[if !supportLists]（1） [endif]若a[low...high]中只有一个元素，则max1 = a[low],max2 = -INF-(-oo)。
[if !supportLists]（2） [endif]若a[low...high]中只有两个元素，则max1 = max{a[low],a[high]},max2=min{a[low],a[high]}。
[if !supportLists]（3） [endif]若a[low...high]中有两个以上元素，按中心位置mid = (low + high)/2分别为a[low...mid]和a[mid + 1...high]两个区间（留意左区间包罗a[mid]元素）。求出左区间的最大元素lmax1和次大元素lmax2，求出右区间的最大元素rmax1和次大元素rmax2。
若lmax1 > rmax1，则max1 = lmax1，max2 = max{lmax2，rmax1}；否则max1 = rmax1,max2 = max{lmax1,rmax2}。
例如：
对于a[0...4] = {5,2,1,4,3},mid = (0 + 4)/2 = 2，分别为左区间a[0...2] = {5,2,1}，右区间a[3...4] = {4,3}。在左区间中求出lmax1 = 5,lmax2 = 2，在右区间中求出rmax = 4，rmax2 = 3。以是max1 = max{lmax1,rmax1} = 5,max2
= max{lmax2,rmax1} = 4。
对于solve(a,0,n-1,max1,max2)调用，假设实在行时间为T(n)，当n=1或2时，起实行此数为1，当n>2时，不绝分解n并递归调用其solve方法，直至n=1或2，其比力次数的递推式如下：
T(1) = T(2) = 1
T(n) = 2T(n/2) + 1 //n>2，归并的时间为O(1)
可以推导出T(n) = O(n)。 |
