maxmin(分治法)

【#文档大全网# 导语】以下是®文档大全网的小编为您整理的《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

nn

T()T()2 n>2

22

在最坏情况下，递归求最大最小元素比第一种算法要好一些，平均情况下两者差不多。当n是2的幂时，即对于某个正整数k，n2k，可以证明，任何以

3n

元素比较为基础的找最大和最小元素的算法，其元素比较下界均为－2次。

2n

T(n)2T()2

2n

2(2T(2)2)2

2n

4T(2)42

2

本文来源：https://www.wddqxz.cn/125435eb2b160b4e767fcfb7.html