阿狗工具

分治法是指将一个复杂的，规模为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)。