maxmin(分治法)
说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。
用分治法（二分法）可以用较少的比较次数解决上述问题。 问题可简化为如下三个步骤： （1）将数据等分为两组（两组数据可能差1），目的是分别选取其中的最大和最小值。 （2）递归分解直到每组元素的个数2，可简单地找到最大和最小值。 （3）回溯时合并子问题的解，在两个子问题的解中大者取大，小者取小，即合并为当前问题的解。 递归求取数组a中最大和最小元素的算法如下： maxmin（i, j , fmax, fmin） float A[n]; maxmin（i, j, fmax, fmin） //最大和最小元素赋给fmax和fmin { if (i==j) { fmax A[i];fmin A[i];} // 每组元素的个数=1时 else if (i==j-1) if (A[i]
{ fmax A[j]；fmin A[i]}
// 每组元素的个数=2时
else
{ fmax A[i]; fmin A[j]; } else
{ mid (i+j)/2;
maxmin(i，mid，lmax，lmin) maxmin(mid+1，j，rmax，rmin） if (lmax > rmax) fmax lmax; else
fmax =rmax;
if (lmin > rmin) fmin rmin; else
fmin =lmin;
} }
例2.3.3.2在下述9个元素上模拟递归求最大和最小元素的过程。
数组A[1..9]的各个元素如下: (1) 22
(2) 13
(3) -5
(4) -8
(5) 15
(6) 60
(7) 17
(8) 31
(9) 47
1，9，60，-8 9
5 8
1，5，22，-8 6，9，60，17
3 4 6 7 1，3，22，-5 4，5，15，-8 6，7，60，17 8，9，47，31
2 1
1，2，22，13 3，3，-5，-5
如果用T（n）表示maxmin中元素比较次数，则所导出的递归关系式是： 0 n=1
T(n) 1 n=2
nn
T()T()2 n>2
22
在最坏情况下，递归求最大最小元素比第一种算法要好一些，平均情况下两者差不多。当n是2的幂时，即对于某个正整数k，n2k，可以证明，任何以
3n
元素比较为基础的找最大和最小元素的算法，其元素比较下界均为－2次。
2n
T(n)2T()2
2n
2(2T(2)2)2
2n
4T(2)42
2
本文来源：https://www.wddqw.com/doc/125435eb2b160b4e767fcfb7.html