分而治之算法简介 - 数据结构和算法教程

在本文中，我们将讨论分而治之技术的作用以及如何使用 DAC 技术方法解决问题。在本节中，我们将讨论以下主题。

DAC简介。
DAC技术下的算法。
DAC算法的递归关系。
使用DAC技术的问题。

分而治之
这种技术可以分为以下三个部分：

划分：这涉及将问题划分为更小的子问题。
征服：通过递归调用解决子问题，直至解决。
组合：将子问题组合起来，得到整个问题的最终解决方案。

以下是遵循分而治之算法的一些标准算法。

快速排序是一种排序算法。该算法选择一个主元元素并重新排列数组元素，以便所有小于所选主元元素的元素都移动到主元的左侧，而所有大于的元素都移动到右侧。最后，算法对主元元素左右两侧的子数组进行递归排序。
归并排序也是一种排序算法。该算法将数组分为两半，对它们进行递归排序，最后合并已排序的两半。
最近的点对问题是在 xy 平面上的一组点中找到最近的点对。通过计算每对点的距离并比较距离以找到最小值，可以在 O(n^2) 时间内解决该问题。分而治之算法可以在 O(N log N) 时间内解决问题。
施特拉森算法是一种有效的两个矩阵相乘算法。两个矩阵相乘的简单方法需要 3 个嵌套循环，时间复杂度为 O(n^3)。Strassen 的算法在 O(n^2.8974) 时间内将两个矩阵相乘。
Cooley-Tukey 快速傅立叶变换 (FFT) 算法是最常见的 FFT 算法。它是一种分而治之的算法，运行时间为 O(N log N)。
Karasuba 快速乘法算法最多可以完成两个n位数字的乘法

什么不符合分而治之的条件：
二分查找是一种搜索算法。在每个步骤中，算法都会将输入元素 x 与数组中中间元素的值进行比较。如果值匹配，则返回中间的索引。否则，如果 x 小于中间元素，则该算法针对中间元素的左侧递归，否则针对中间元素的右侧递归。

与普遍的看法相反，这不是分而治之的例子，因为每一步只有一个子问题（分而治之要求必须有两个或更多子问题），因此这是一种减少和解决的情况征服。

分而治之算法：

DAC(a, i, j)
{
    if(small(a, i, j))
      return(Solution(a, i, j))
    else 
      mid = divide(a, i, j)               // f1(n)
      b = DAC(a, i, mid)                 // T(n/2)
      c = DAC(a, mid+1, j)            // T(n/2)
      d = combine(b, c)                 // f2(n)
   return(d)
}

DAC 算法的递归关系：这是上述程序的递归关系。

           O(1) if n is small
T(n) =     f1(n) + 2T(n/2) + f2(n)

示例：
查找给定数组中的最大和最小元素。
输入： { 70, 250, 50, 80, 140, 12, 14 }
输出：给定数组中的最小数字为：12
给定数组中的最大数字为：250

方法：从给定数组中查找最大和最小元素是分而治之的应用。在这个问题中，我们将找到给定数组中的最大和最小元素。在这个问题中，我们使用分而治之的方法（DAC），它具有分治、分治和组合三个步骤。

对于最大值：
在这个问题中，我们使用递归方法来查找最大值，我们将看到只剩下两个元素，然后我们可以轻松使用条件，即 if(a[index]>a[index+1].)
在程序行中，a[index]和a[index+1])条件将确保左侧只有两个元素。

if(index >= l-2) 
{ 
if(a[index]>a[index+1]) 
{ 
// (a[index] 
// 现在，我们可以说最后一个元素将是给定数组中的最大值. 
} 
else 
{ 
//(a[index+1] 
// 现在，我们可以说最后一个元素将是给定数组中的最大值。 
}
}

在上述条件中，我们检查了左侧条件以找出最大值。现在，我们将看到右侧条件来找到最大值。
用于检查数组当前索引右侧的递归函数。

max = DAC_Max(a, 索引+1, l); 
// 递归调用

现在，我们将比较条件并检查给定数组当前索引处的右侧。
在给定的程序中，我们将实现此逻辑来检查当前索引右侧的条件。

// 右边的元素将是最大的。 
if(a[index]>max) 
返回 a[index];
// max 将是给定数组中的最大元素。 
否则 
返回最大值； 
}

对于最小值：
在这个问题中，我们将实现递归方法来找到最小值。在给定的数组中。

int DAC_Min(int a, int index, int l) 
//递归调用函数求最小值。在给定的数组中。
if(index >= l-2) 
// 检查左侧是否有两个元素， 
然后我们可以轻松找到给定数组中的最小元素。 
{ 
// 这里我们将检查条件 
if(a[index]<a[index+1]) 
return a[index]; 
否则 
返回a[索引+1]； 
}

现在，我们将检查给定数组右侧的条件。

// 递归调用给定数组的右侧。 
min = DAC_Min(a, 索引+1, l);

现在，我们将检查条件以找到右侧的最小值。

// 右侧元素为最小值 
if(a[index]<min) 
return a[index]; 
// 这里 min 将是给定数组中的最小值。 
否则 
返回min ；

Java代码

// 演示除法和
//征服算法的 Java 代码
class GFG{

// 函数用于查找给定数组中的最大数
//。
static int DAC_Max(int a, int index, int l)
{
    int max;
    if(l - 1 == 0)
    {
    return a[index];
    }
    if (index >= l - 2) 
    {
        if (a[index] > a[index + 1])
            return a[index];
        else
            return a[index + 1];
    }

// 在给定数组中查找最大元素的逻辑
    //。
    max = DAC_Max(a, index + 1, l);

if (a[index] > max)
        return a[index];
    else
        return max;
}

// 函数用于查找给定数组中的最小数
//。
static int DAC_Min(int a, int index, int l)
{
    int min;
    if(l - 1 == 0)
    {
    return a[index];
    }
    if (index >= l - 2)
    {
        if (a[index] < a[index + 1])
            return a[index];
        else
            return a[index + 1];
    }

// 在给定数组中查找最小元素
    // 的逻辑。
    min = DAC_Min(a, index + 1, l);

if (a[index] < min)
        return a[index];
    else
        return min;
}

// Driver Code
public static void main(String args)
{

// Defining the variables
    int min, max;

// Initializing the array
    int a = { 70, 250, 50, 80, 140, 12, 14 };

// Recursion - DAC_Max function called
    max = DAC_Max(a, 0, 7);

// Recursion - DAC_Max function called
    min = DAC_Min(a, 0, 7);

System.out.printf("The minimum number in " +
                    "a given array is : %d\n", min);
    System.out.printf("The maximum number in " +
                    "a given array is : %d", max);
}
}

Python代码

# Python3 code to demonstrate Divide and
# Conquer Algorithm

# Function to find the maximum no.
# in a given array.


def DAC_Max(a, index, l):
    max = -1
    if(l - 1 == 0):
        return arr[index]
    if (index >= l - 2):
        if (a[index] > a[index + 1]):
            return a[index]
        else:
            return a[index + 1]

# Logic to find the Maximum element
    # in the given array.
    max = DAC_Max(a, index + 1, l)

if (a[index] > max):
        return a[index]
    else:
        return max

# Function to find the minimum no.
# in a given array.


def DAC_Min(a, index, l):
    min = 0
    if(l - 1 == 0):
        return arr[index]
    if (index >= l - 2):
        if (a[index] < a[index + 1]):
            return a[index]
        else:
            return a[index + 1]

# Logic to find the Minimum element
    # in the given array.
    min = DAC_Min(a, index + 1, l)

if (a[index] < min):
        return a[index]
    else:
        return min


# Driver Code
if __name__ == '__main__':

# Defining the variables
    min, max = 0, -1

# Initializing the array
    a = [70, 250, 50, 80, 140, 12, 14]

# Recursion - DAC_Max function called
    max = DAC_Max(a, 0, 7)

# Recursion - DAC_Max function called
    min = DAC_Min(a, 0, 7)
    print("The minimum number in a given array is : ", min)
    print("The maximum number in a given array is : ", max)

Java中用Fork-Join查找给定数组中的最大和最小元素

在Java中，可以使用Fork-Join框架来并行地查找给定数组中的最大和最小元素。Fork-Join框架提供了一种方便的方式来执行递归任务，并通过分治的方式将任务拆分成子任务，从而实现并行计算。

以下是一个使用Fork-Join框架查找数组中最大和最小元素的示例代码：

import java.util.concurrent.RecursiveTask;
import java.util.concurrent.ForkJoinPool;

public class MaxMinFinder extends RecursiveTask<MinMaxResult> {
    private static final int THRESHOLD = 500; // 阈值，控制任务拆分的大小
    private int array;
    private int start;
    private int end;

public MaxMinFinder(int array, int start, int end) {
        this.array = array;
        this.start = start;
        this.end = end;
    }

@Override
    protected MinMaxResult compute() {
        int length = end - start + 1;

if (length <= THRESHOLD) {
            // 如果任务足够小，直接计算最大和最小值
            int min = array[start];
            int max = array[start];
            for (int i = start + 1; i <= end; i++) {
                if (array[i] [/i]< min) {
                    min = array;
                }
                if (array > max) {
                    max = array;
                }
            }
            return new MinMaxResult(min, max);
        } else {
            // 如果任务太大，拆分为两个子任务并递归地执行
            int mid = start + (end - start) / 2;
            MaxMinFinder leftTask = new MaxMinFinder(array, start, mid);
            MaxMinFinder rightTask = new MaxMinFinder(array, mid + 1, end);

// 并行执行子任务
            invokeAll(leftTask, rightTask);

// 合并子任务的结果
            MinMaxResult leftResult = leftTask.join();
            MinMaxResult rightResult = rightTask.join();

// 合并最小和最大值
            int min = Math.min(leftResult.getMin(), rightResult.getMin());
            int max = Math.max(leftResult.getMax(), rightResult.getMax());

return new MinMaxResult(min, max);
        }
    }

public static void main(String args) {
        int array = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};

ForkJoinPool forkJoinPool = new ForkJoinPool();
        MaxMinFinder task = new MaxMinFinder(array, 0, array.length - 1);
        MinMaxResult result = forkJoinPool.invoke(task);

System.out.println("Min: " + result.getMin());
        System.out.println("Max: " + result.getMax());
    }
}

class MinMaxResult {
    private final int min;
    private final int max;

public MinMaxResult(int min, int max) {
        this.min = min;
        this.max = max;
    }

public int getMin() {
        return min;
    }

public int getMax() {
        return max;
    }
}

在这个示例中，MaxMinFinder类是一个RecursiveTask，它负责查找数组中的最大和最小值。在compute方法中，如果任务足够小（小于等于阈值），则直接计算最大和最小值；否则，将任务拆分为两个子任务，并通过invokeAll并行执行这两个子任务。然后，通过join方法等待子任务完成并获取其结果，最终合并子任务的结果得到整体的最小和最大值。在main方法中，创建一个ForkJoinPool实例，并通过invoke方法启动任务并获取结果。

分而治之算法简介 - 数据结构和算法教程

分而治之算法简介 - 数据结构和算法教程

Recommend

令人惊叹的 Grafana 仪表盘用途：2023 年最有创意和有趣的用例分享

MacOS Sonoma14.2.1系统SSH免密登录 - Mr老刘

Scotland rescue group adds DJI FPV drone to its search toolbox

Unlocking AI/ML Potential: A Practical Guide for Business Leaders

Here's How Samsung's New Android Battery Protection Feature Is Supposed To Work

World's tallest wooden wind turbine starts turning

5 Must-Have Home Depot Tools For Every Home Garage

auto{x}与auto(x)---一位中国小伙为cppreference作出的贡献 - ChebyshevTST

Infinix XW2 智能手表通过 SDPPI 认证，可能即将推出

Year in Review 2023: How did CRIME De-Coder do?

About Joyk