Data Structures Algorithms 简明教程

Max-Min Problem

让我们考虑一个可以通过分治法解决的简单问题。

Let us consider a simple problem that can be solved by divide and conquer technique.

Max-Min Problem

算法分析中的最大最小问题是找到数组中的最大值和最小值。

The Max-Min Problem in algorithm analysis is finding the maximum and minimum value in an array.

Solution

要找到给定大小为 n 的数组 numbers[] 中的最大值和最小值，可以使用以下算法。首先我们用 naive method 表示，然后我们用 divide and conquer approach 表示。

To find the maximum and minimum numbers in a given array numbers[] of size n, the following algorithm can be used. First we are representing the naive method and then we will present divide and conquer approach.

Naive Method

朴素方法是解决任何问题的基本方法。在此方法中，可以分别找到最大值和最小值。要找到最大值和最小值，可以使用以下简单的算法。

Naive method is a basic method to solve any problem. In this method, the maximum and minimum number can be found separately. To find the maximum and minimum numbers, the following straightforward algorithm can be used.

Algorithm: Max-Min-Element (numbers[])
max := numbers[1]
min := numbers[1]

for i = 2 to n do
   if numbers[i] > max then
      max := numbers[i]
   if numbers[i] < min then
      min := numbers[i]
return (max, min)

Example

以下是不同编程语言中上述方法的实现 -

Following are the implementations of the above approach in various programming languages −

Analysis

朴素方法中的比较次数为 2n - 2 。

The number of comparison in Naive method is 2n - 2.

可以使用分治法来减少比较次数。以下为该方法。

The number of comparisons can be reduced using the divide and conquer approach. Following is the technique.

Divide and Conquer Approach

在这种方法中，将数组分成两半。然后使用递归方法找到每一半中的最大值和最小值。随后，返回每一半的两个最大值的较大者和每一半的两个最小值的较小者。

In this approach, the array is divided into two halves. Then using recursive approach maximum and minimum numbers in each halves are found. Later, return the maximum of two maxima of each half and the minimum of two minima of each half.

在这个给定问题中，数组中的元素数量为 $y - x + 1$，其中 y 大于或等于 x 。

In this given problem, the number of elements in an array is $y - x + 1$, where y is greater than or equal to x.

$\mathbf{\mathit{Max - Min(x, y)}}$ 将返回数组 $\mathbf{\mathit{numbers[x…y]}}$ 的最大值和最小值。

$\mathbf{\mathit{Max - Min(x, y)}}$ will return the maximum and minimum values of an array $\mathbf{\mathit{numbers[x…y]}}$.

Algorithm: Max - Min(x, y)
if y – x ≤ 1 then
   return (max(numbers[x],numbers[y]),min((numbers[x],numbers[y]))
else
   (max1, min1):= maxmin(x, ⌊((x + y)/2)⌋)
   (max2, min2):= maxmin(⌊((x + y)/2) + 1)⌋,y)
return (max(max1, max2), min(min1, min2))

Example

以下是各种编程语言中上述算法的实现 −

Following are implementations of the above approach in various programming languages −

Analysis

令 T(n) 为 $\mathbf{\mathit{Max - Min(x, y)}}$ 进行的比较次数，其中元素数目 $n = y - x + 1$。

Let T(n) be the number of comparisons made by $\mathbf{\mathit{Max - Min(x, y)}}$, where the number of elements $n = y - x + 1$.

如果 T(n) 表示数字，则递推关系可以表示为

If T(n) represents the numbers, then the recurrence relation can be represented as

T(n) = \begin{cases}T\left(\lfloor\frac{n}{2}\rfloor\right)+T\left(\lceil\frac{n}{2}\rceil\right)+2 & for\: n>2\\1 & for\:n = 2 \\0 & for\:n = 1\end{cases}

让我们假设 n 采用 2 的幂的形式。因此， n = 2k 其中 k 是递归树的高度。

Let us assume that n is in the form of power of 2. Hence, n = 2k where k is height of the recursion tree.

所以，

So,

T(n) = 2.T (\frac{n}{2}) + 2 = 2.\left(\begin{array}{c}2.T(\frac{n}{4}) + 2\end{array}\right) + 2 ….. = \frac{3n}{2} - 2

与朴素方法相比，分治算法的比较次数较少。但是，使用渐近符号表示，这两种算法都用 O(n) 表示。

Compared to Naïve method, in divide and conquer approach, the number of comparisons is less. However, using the asymptotic notation both of the approaches are represented by O(n).