4 找最大和最小元素.doc

4 找最大和最小元素 如果要在含有n个不同元素的集合中同时找出它的最大和最小元素(元素类型为elemType，可比较大小)，最简单的方法是将元素逐个进行比较。这种直接算法可初步描述如下。 算法4.1 直接找最大和最小元素 void StraitMaxMin(elemType a[]，int n，elemType Max，elemType Min) { // 将A(1：n)中的最大元素置于max中，最小元素置于min中。 int i； Max=Min=a[1]； For(i=2；i=n；++i) { if(a[i]max) Max=a[i]； if(a[i]max) Min=a[i]； }；//for }// StraitMaxMin 分析这个算法的时间复杂度时，只需将元素比较次数求出即可。这不仅是因为算法中的其它运算与元素比较有相同数量级的频率计数，而且更重要的是，当A(l：n)中的元素是多项式、向量、非常大的数或字符串时，一次元素比较所用的时间比其它运算的时间多得多。 容易看出过程StraitMaxMin在最好、平均和最坏情况下均需要作2(n-l)次元素比较。另外，只要考察一下算法4.1就可发现，只有当A(i)max为假时，才有必要比较A(i)min，因此，可用下面的语句代替for循环中的语句： if(a[i]max) Max=a[i]； else if(a[i]Min) Min=a[i]； 在作以上改进后，最好情况将在元素按递增次序排列时出现，元素比较数是n-1；最坏情况将在递减次序时出现，元素比较数是2(n-1)；至于平均情况，A(i)将有一半的数据比max大，因此平均比较数是3*(n-1)/2（即上述两种情况的平均值）。 能否找到更好的算法呢？下面用分治策略的思想来设计一个算法与直接算法作比较。使用分治策略设计是将某一实例I=(n，A(l)，…，A(n))分成一些较小的实例来处理。例如，可以把I分成两个实例：I1=(「n/2」，A(1)，…，A(「n/2」))和I2=(n-「n/2」，A(「n/2」+1)，…，A(n))。如果Max(I)和 Min(I)是I中的最大和最小元素，则Max(I)等于Max(I1)和Max(I2)中的较大者，而Min(I)等于Min(I1)和Min(I2)中的较者。如果I只包含一个元素，则不需要作任何分割，直接就可得到其解。 算法4.2依据以上方法所编写的函数，它是在元素集合｛A(i)，A(i＋1)，…，A(j)｝中找最大和最小元素的递归过程。函数对于集合中含有一个元素(i=j)和两个元素(i=j-1)的情况分别作了处理，而对含有多于两个元素的集合，则确定其中点(正如在二分检索中那样作分割)，并且产生两个新的子问题。当分别找到这两个子问题的最大和最小值后，再比较这两个最大值和两个最小值，最终得到此全集合的解。Max和Min被看成是两个内部函数，它们分别求取两个元素的大者和小者，并认为每次调用其中的一个函数都只需作一次元素比较。 算法4.2 递归求取最大和最小元素 VOID MaxMin(int i，int j，elemType fmax，elemType fmin) { // A(1：n)是含有n个元素的数组，参数i，j是整数（1≤i，j≤n） //该函数把A(i，j)中的最大和最小元素分别赋给fmax和fmin。 int A[]，n； //n和数组A（1，n）说明成全程变量。 if(i==j) {fmax=fmin=a[i]；return fmax，fmin；} if(i==j-1) { if(a[i]a[j]) {fmax=a[j]；fmin=a[i]；} else {fmax=a[i]；fmin=a[j]；} return fmax，fmin； }；//if mid = (i+j) ／2； MaxMin(i，mid，gmax，gmin)； MaxMin(mid+1，j，hmax，hmin)； fmax=max(gmax，hmax)； fmin=min(gmin，hmin)； return fmax，fmin； }；//MaxMin 这个函数过程最初由调用MaxMin(l，n，x，y)实现。为加深对这个过程的理解，请看下面的例子。 例4.1 在下述九个元素上模拟函数过程MaxMin。 a[1..9]：[l] [2] [3] [4] [5] [6] [7] [8] [9] 22 13 -5 -8 15 60 17 31 47 用一棵树来描述递归调用的轨迹是很清晰的，其中的一个结点表示一次递归调用，每作一次新的调用就增加一个结点。对于这个程序来说，每个结点有四项信息：i，j，fmax，fmin。根据上面的数组 a[]，就可画出图4.1所示的树。图中，根