Data Structures Algorithms 简明教程

Max-Min Problem

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

Max-Min Problem

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

Solution

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

Naive Method

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

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

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

Analysis

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

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

Divide and Conquer Approach

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

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

$\mathbf{\mathit{Max - Min(x, y)}}$ 将返回数组 $\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

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

Analysis

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

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

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 是递归树的高度。

所以，

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) 表示。