最大最小问题
我们考虑一个可以用分治法解决的简单问题。
最大最小问题
算法分析中的最大最小问题是在数组中找出最大值和最小值。
解决方案
在给定数组中找出最大值和最小值对于大小为 n 的 numbers[]，可以使用以下算法。首先，我们介绍朴素方法，然后介绍分而治之方法。
朴素方法
朴素方法是解决任何问题的基本方法。在这种方法中，可以分别找到最大值和最小值。要找到最大值和最小值，可以使用以下简单的算法。
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)
示例
以下是上述方法在各种编程语言中的实现 −
#include <stdio.h>
struct Pair {
int max;
int min;
};
// 使用朴素算法查找最大值和最小值的函数
struct Pair maxMinNaive(int arr[], int n) {
struct Pair result;
result.max = arr[0];
result.min = arr[0];
// 循环遍历数组以找到最大值和最小值
for (int i = 1; i < n; i++) {
if (arr[i] > result.max) {
result.max = arr[i]; // 如果找到更大的元素，则更新最大值
}
if (arr[i] < result.min) {
result.min = arr[i]; // 如果找到较小的元素，则更新最小值
}
}
return result; // 返回最大值和最小值对
}
int main() {
int arr[] = {6, 4, 26, 14, 33, 64, 46};
int n = sizeof(arr) / sizeof(arr[0]);
struct Pair result = maxMinNaive(arr, n);
printf("最大元素为： %d
", result.max);
printf("最小元素为： %d
", result.min);
return 0;
}
输出
最大元素为： 64 最小元素为： 4
#include <iostream>
using namespace std;
struct Pair {
int max;
int min;
};
// 使用朴素算法查找最大值和最小值的函数
Pair maxMinNaive(int arr[], int n) {
Pair result;
result.max = arr[0];
result.min = arr[0];
// 循环遍历数组以找到最大值和最小值
for (int i = 1; i < n; i++) {
if (arr[i] > result.max) {
result.max = arr[i]; // 如果找到更大的元素，则更新最大值
}
if (arr[i] < result.min) {
result.min = arr[i]; // 如果找到较小的元素，则更新最小值
}
}
return result; // 返回最大值和最小值对
}
int main() {
int arr[] = {6, 4, 26, 14, 33, 64, 46};
int n = sizeof(arr) / sizeof(arr[0]);
Pair result = maxMinNaive(arr, n);
cout << "最大元素为： " << result.max << endl;
cout << "最小元素为： " << result.min << endl;
return 0;
}
输出
最大元素为： 64 最小元素为： 4
public class MaxMinNaive {
static class Pair {
int max;
int min;
}
// 使用朴素算法查找最大值和最小值的函数
static Pair maxMinNaive(int[] arr) {
Pair result = new Pair();
result.max = arr[0];
result.min = arr[0];
// 循环遍历数组以找到最大值和最小值
for (int i = 1; i < arr.length; i++) {
if (arr[i] > result.max) {
result.max = arr[i]; // 如果找到更大的元素，则更新最大值
}
if (arr[i] < result.min) {
result.min = arr[i]; // 如果找到较小的元素，则更新最小值
}
}
return result; // 返回最大值和最小值对
}
public static void main(String[] args) {
int[] arr = {6, 4, 26, 14, 33, 64, 46};
Pair result = maxMinNaive(arr);
System.out.println("最大元素为： " + result.max);
System.out.println("最小元素为： " + result.min);
}
}
输出
最大元素为： 64 最小元素为： 4
def max_min_naive(arr):
max_val = arr[0]
min_val = arr[0]
# 循环遍历数组以找到最大值和最小值
for i in range(1, len(arr)):
if arr[i] > max_val:
max_val = arr[i] # 如果找到更大的元素，则更新最大值
if arr[i] < min_val:
min_val = arr[i] # 如果找到较小的元素，则更新最小值
return max_val, min_val # 返回最大值和最小值对
arr = [6, 4, 26, 14, 33, 64, 46]
max_val, min_val = max_min_naive(arr)
print("最大元素为：", max_val)
print("最小元素为：", min_val)
输出
最大元素为： 64 最小元素为： 4
分析
朴素方法的比较次数为 2n - 2。
可以使用分治法减少比较次数。以下是具体技巧。
分治法
在这种方法中，将数组分成两半。然后使用递归方法找出每半中的最大值和最小值。然后，返回每半部分的两个最大值中的最大值，以及每半部分的两个最小值中的最小值。
在这个给定的问题中，数组中的元素数量为 $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))
示例
以下是上述方法在各种编程语言中的实现 −
#include <stdio.h>
// 存储最大和最小元素的结构
struct Pair {
int max;
int min;
};
struct Pair maxMinDivideConquer(int arr[], int low, int high) {
struct Pair result;
struct Pair left;
struct Pair right;
int mid;
// 如果数组中只有一个元素
if (low == high) {
result.max = arr[low];
result.min = arr[low];
return result;
}
// 如果数组中有两个元素
if (high == low + 1) {
if (arr[low] < arr[high]) {
result.min = arr[low];
result.max = arr[high];
} else {
result.min = arr[high];
result.max = arr[low];
}
return result;
}
// 如果数组中有两个以上的元素
mid = (low + high) / 2;
left = maxMinDivideConquer(arr, low, mid);
right = maxMinDivideConquer(arr, mid + 1, high);
// 比较并取两部分的最大值
result.max = (left.max > right.max) ? left.max : right.max;
// 比较并取两部分的最小值
result.min = (left.min < right.min) ? left.min : right.min;
return result;
}
int main() {
int arr[] = {6, 4, 26, 14, 33, 64, 46};
int n = sizeof(arr) / sizeof(arr[0]);
struct Pair result = maxMinDivideConquer(arr, 0, n - 1);
printf("最大元素为： %d
", result.max);
printf("最小元素为： %d
", result.min);
return 0;
}
输出
最大元素为： 64 最小元素为： 4
#include <iostream>
using namespace std;
// 存储最大和最小元素的结构
struct Pair {
int max;
int min;
};
Pair maxMinDivideConquer(int arr[], int low, int high) {
Pair result, left, right;
int mid;
// 如果数组中只有一个元素
if (low == high) {
result.max = arr[low];
result.min = arr[low];
return result;
}
// 如果数组中有两个元素
if (high == low + 1) {
if (arr[low] < arr[high]) {
result.min = arr[low];
result.max = arr[high];
} else {
result.min = arr[high];
result.max = arr[low];
}
return result;
}
// 如果数组中有两个以上的元素
mid = (low + high) / 2;
left = maxMinDivideConquer(arr, low, mid);
right = maxMinDivideConquer(arr, mid + 1, high);
// 比较并取两部分的最大值
result.max = (left.max > right.max) ? left.max : right.max;
// 比较并取两部分的最小值
result.min = (left.min < right.min) ? left.min : right.min;
return result;
}
int main() {
int arr[] = {6, 4, 26, 14, 33, 64, 46};
int n = sizeof(arr) / sizeof(arr[0]);
Pair result = maxMinDivideConquer(arr, 0, n - 1);
cout << "最大元素为： " << result.max << endl;
cout << "最小元素为： " << result.min << endl;
return 0;
}
输出
最大元素为： 64 最小元素为： 4
public class MaxMinDivideConquer {
// 存储最大和最小元素的类
static class Pair {
int max;
int min;
}
static Pair maxMinDivideConquer(int[] arr, int low, int high) {
Pair result = new Pair();
Pair left, right;
int mid;
// 如果数组中只有一个元素
if (low == high) {
result.max = arr[low];
result.min = arr[low];
return result;
}
// 如果数组中有两个元素
if (high == low + 1) {
if (arr[low] < arr[high]) {
result.min = arr[low];
result.max = arr[high];
} else {
result.min = arr[high];
result.max = arr[low];
}
return result;
}
// 如果数组中有两个以上的元素
mid = (low + high) / 2;
left = maxMinDivideConquer(arr, low, mid);
right = maxMinDivideConquer(arr, mid + 1, high);
// 比较并取两部分的最大值
result.max = Math.max(left.max, right.max);
// 比较并取两部分的最小值
result.min = Math.min(left.min, right.min);
return result;
}
public static void main(String[] args) {
int[] arr = {6, 4, 26, 14, 33, 64, 46};
Pair result = maxMinDivideConquer(arr, 0, arr.length - 1);
System.out.println("最大元素为： " + result.max);
System.out.println("最小元素为： " + result.min);
}
}
输出
最大元素为： 64 最小元素为： 4
def max_min_divide_conquer(arr, low, high):
# 存储最大和最小元素的结构
class Pair:
def __init__(self):
self.max = 0
self.min = 0
result = Pair()
# 如果数组中只有一个元素
if low == high:
result.max = arr[low]
result.min = arr[low]
return result
# 如果数组中有两个元素
if high == low + 1:
if arr[low] < arr[high]:
result.min = arr[low]
result.max = arr[high]
else:
result.min = arr[high]
result.max = arr[low]
return result
# 如果数组中有两个以上的元素
mid = (low + high) // 2
left = max_min_divide_conquer(arr, low, mid)
right = max_min_divide_conquer(arr, mid + 1, high)
# 比较并取两部分的最大值
result.max = max(left.max, right.max)
# 比较并取两部分的最小值
result.min = min(left.min, right.min)
return result
arr = [6, 4, 26, 14, 33, 64, 46]
result = max_min_divide_conquer(arr, 0, len(arr) - 1)
print("最大元素为：", result.max)
print("最小元素为：", result.min)
输出
最大元素为： 64 最小元素为： 4
分析
设 T(n) 为 $\mathbf{\mathit{Max - Min(x, y)}}$ 进行的比较次数，其中元素个数 $n = y - x + 1$。
如果 T(n) 表示数字，则递归关系可以表示为
$$T(n) = \begin{cases}T\left(\lfloor\frac{n}{2} floor ight)+T\left(\lceil\frac{n}{2} ceil ight)+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)。
