最大最小值問題

Table of content
上一頁
下一頁

讓我們考慮一個可以用分治法解決的簡單問題。

最大最小值問題

演算法分析中的最大最小值問題是在陣列中查詢最大值和最小值。

解決方案

為了在一個大小為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)

示例

以下是上述方法在各種程式語言中的實現：

C C++ Java Python
#include <stdio.h>
struct Pair {
    int max;
    int min;
};
// Function to find maximum and minimum using the naive algorithm
struct Pair maxMinNaive(int arr[], int n) {
    struct Pair result;
    result.max = arr[0];
    result.min = arr[0];
    // Loop through the array to find the maximum and minimum values
    for (int i = 1; i < n; i++) {
        if (arr[i] > result.max) {
            result.max = arr[i]; // Update the maximum value if a larger element is found
        }
        if (arr[i] < result.min) {
            result.min = arr[i]; // Update the minimum value if a smaller element is found
        }
    }
    return result; // Return the pair of maximum and minimum values
}
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("Maximum element is: %d\n", result.max);
    printf("Minimum element is: %d\n", result.min);
    return 0;
}

輸出

Maximum element is: 64
Minimum element is: 4

#include <iostream>
using namespace std;
struct Pair {
    int max;
    int min;
};
// Function to find maximum and minimum using the naive algorithm
Pair maxMinNaive(int arr[], int n) {
    Pair result;
    result.max = arr[0];
    result.min = arr[0];
    // Loop through the array to find the maximum and minimum values
    for (int i = 1; i < n; i++) {
        if (arr[i] > result.max) {
            result.max = arr[i]; // Update the maximum value if a larger element is found
        }
        if (arr[i] < result.min) {
            result.min = arr[i]; // Update the minimum value if a smaller element is found
        }
    }
    return result; // Return the pair of maximum and minimum values
}
int main() {
    int arr[] = {6, 4, 26, 14, 33, 64, 46};
    int n = sizeof(arr) / sizeof(arr[0]);
    Pair result = maxMinNaive(arr, n);
    cout << "Maximum element is: " << result.max << endl;
    cout << "Minimum element is: " << result.min << endl;
    return 0;
}

輸出

Maximum element is: 64
Minimum element is: 4

public class MaxMinNaive {
    static class Pair {
        int max;
        int min;
    }
    // Function to find maximum and minimum using the naive algorithm
    static Pair maxMinNaive(int[] arr) {
        Pair result = new Pair();
        result.max = arr[0];
        result.min = arr[0];
        // Loop through the array to find the maximum and minimum values
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > result.max) {
                result.max = arr[i]; // Update the maximum value if a larger element is found
            }
            if (arr[i] < result.min) {
                result.min = arr[i]; // Update the minimum value if a smaller element is found
            }
        }
        return result; // Return the pair of maximum and minimum values
    }
    public static void main(String[] args) {
        int[] arr = {6, 4, 26, 14, 33, 64, 46};
        Pair result = maxMinNaive(arr);
        System.out.println("Maximum element is: " + result.max);
        System.out.println("Minimum element is: " + result.min);
    }
}

輸出

Maximum element is: 64
Minimum element is: 4

def max_min_naive(arr):
    max_val = arr[0]
    min_val = arr[0]
    # Loop through the array to find the maximum and minimum values
    for i in range(1, len(arr)):
        if arr[i] > max_val:
            max_val = arr[i]  # Update the maximum value if a larger element is found
        if arr[i] < min_val:
            min_val = arr[i]  # Update the minimum value if a smaller element is found
    return max_val, min_val  # Return the pair of maximum and minimum values
arr = [6, 4, 26, 14, 33, 64, 46]
max_val, min_val = max_min_naive(arr)
print("Maximum element is:", max_val)
print("Minimum element is:", min_val)

輸出

Maximum element is: 64
Minimum element is: 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))

示例

以下是上述方法在各種程式語言中的實現：

C C++ Java Python
#include <stdio.h>
// Structure to store both maximum and minimum elements
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 only one element in the array
    if (low == high) {
        result.max = arr[low];
        result.min = arr[low];
        return result;
    }
    // If there are two elements in the array
    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;
    }
    // If there are more than two elements in the array
    mid = (low + high) / 2;
    left = maxMinDivideConquer(arr, low, mid);
    right = maxMinDivideConquer(arr, mid + 1, high);
    // Compare and get the maximum of both parts
    result.max = (left.max > right.max) ? left.max : right.max;
    // Compare and get the minimum of both parts
    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("Maximum element is: %d\n", result.max);
    printf("Minimum element is: %d\n", result.min);
    return 0;
}

輸出

Maximum element is: 64
Minimum element is: 4

#include <iostream>
using namespace std;
// Structure to store both maximum and minimum elements
struct Pair {
    int max;
    int min;
};
Pair maxMinDivideConquer(int arr[], int low, int high) {
    Pair result, left, right;
    int mid;
    // If only one element in the array
    if (low == high) {
        result.max = arr[low];
        result.min = arr[low];
        return result;
    }
    // If there are two elements in the array
    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;
    }
    // If there are more than two elements in the array
    mid = (low + high) / 2;
    left = maxMinDivideConquer(arr, low, mid);
    right = maxMinDivideConquer(arr, mid + 1, high);
    // Compare and get the maximum of both parts
    result.max = (left.max > right.max) ? left.max : right.max;
    // Compare and get the minimum of both parts
    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 << "Maximum element is: " << result.max << endl;
    cout << "Minimum element is: " << result.min << endl;
    return 0;
}

輸出

Maximum element is: 64
Minimum element is: 4 

public class MaxMinDivideConquer {
    // Class to store both maximum and minimum elements
    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 only one element in the array
        if (low == high) {
            result.max = arr[low];
            result.min = arr[low];
            return result;
        }
        // If there are two elements in the array
        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;
        }
        // If there are more than two elements in the array
        mid = (low + high) / 2;
        left = maxMinDivideConquer(arr, low, mid);
        right = maxMinDivideConquer(arr, mid + 1, high);
        // Compare and get the maximum of both parts
        result.max = Math.max(left.max, right.max);
        // Compare and get the minimum of both parts
        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("Maximum element is: " + result.max);
        System.out.println("Minimum element is: " + result.min);
    }
}

輸出

Maximum element is: 64
Minimum element is: 4

def max_min_divide_conquer(arr, low, high):
    # Structure to store both maximum and minimum elements
    class Pair:
        def __init__(self):
            self.max = 0
            self.min = 0
    result = Pair()
    # If only one element in the array
    if low == high:
        result.max = arr[low]
        result.min = arr[low]
        return result
    # If there are two elements in the array
    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
    # If there are more than two elements in the array
    mid = (low + high) // 2
    left = max_min_divide_conquer(arr, low, mid)
    right = max_min_divide_conquer(arr, mid + 1, high)
    # Compare and get the maximum of both parts
    result.max = max(left.max, right.max)
    # Compare and get the minimum of both parts
    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("Maximum element is:", result.max)
print("Minimum element is:", result.min)

輸出

Maximum element is: 64
Minimum element is: 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}\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)表示。

列印頁面
上一頁
下一頁
廣告