分治算法
几周前我有一个工作面试，我被要求设计一个分而治之的算法。我无法解决这个问题，但他们只是打电话给我进行第二次面试！问题是：
我们给出了两个n元素数组A[0..n-1]和B[0..n-1]（它们不一定是排序的），以及一个整数值作为输入。给出了一个O（nlogn）分治算法，该算法确定是否存在不同的值i,j（即i！=j)，使得A[i]+B[j]=value。如果i,j存在，算法应返回True，否则返回False。您可以假设A中的元素是不同的，B中的元素是不同的。
有人能解决这个问题吗？谢谢
共有1个答案
我的方法是..
- 对任意数组进行排序。这里我们对数组a进行排序，使用
合并排序算法对其进行排序，该算法是分而治之算法。 - 然后，对于B的每个元素，通过
二进制搜索在数组A中搜索B必需的值元素。同样，这是一个分而治之算法。 - 如果从数组A中找到元素
Required value-b的元素，那么这两个元素就成对，这样A元素+B=Required Value.
因此，为了时间复杂性，A有N元素，因此合并排序将采用O（N log N)，我们对采用O（N log N)的B（总N个元素）的每个元素进行二分搜索。因此，总的时间复杂度为O(N log N)。
正如您所提到的，您需要检查i！=j，如果a[i]+b[j]=value，那么这里您可以使用大小为n*2的2D数组。每个元素与其原始索引成对，作为每行的第二个元素。将根据存储在第一个元素中的数据进行排序。然后，当找到元素时，可以比较两个元素的原始索引并相应地返回值。
-
主要内容：分治算法的利弊,分治算法的应用场景实际场景中，我们之所以觉得有些问题很难解决，主要原因是该问题涉及到大量的数据，如果只需要处理少量的数据，问题会变得非常容易解决。 举一个简单的例子，设计一个排序算法实现对 1000 个整数进行排序。对于很多刚刚接触算法的初学者来说，直接实现对 1000 个整数进行排序是非常困难的。而同样的问题，如果转换成对 2 个整数进行排序，解决起来就很容易。 分治算法中，“分治”即“分而治之”的意思。分治算法
-
这学期我们学习了分而治之，在分而治之中，问题被分成子问题，然后像合并排序或快速排序一样解决。 虽然我发布这个问题不是为了让你们解决我的作业，我们的教授给了我们一个任务，让我们把冒泡排序作为一种分治算法来实现，现在我坐在笔记本电脑上，几天都在挠头，想知道冒泡排序是如何分治算法的。 如果我试图将冒泡排序实现为分治，数组必须被分割，当我将数组划分为最后一个元素，然后将其合并回已排序的形式时，算法就变成了
-
分治和回溯其实本质上就是递归，只不过它是递归的其中一个细分类。可以认为 分治和回溯 最后就是 一种特殊的递归 或者是较为复杂的递归即可。 分治算法，即分而治之（divide and conquer，D&C），把 一个复杂问题 分成 两个或更多 的相同或相似 子问题，直到最后子问题可以简单地直接求解，最后将子问题的解合并为原问题的解。 分治法的核心思想就是，将原问题分解成小问题来求解，只要遵循三个步
-
如果数组中一半以上的元素相同，则称数组具有多数元素。是否有一种分治算法来确定数组是否具有多数元素？ 我通常会执行以下操作，但它不是使用“分而治之”。我不想使用Boyer-Moore算法。
-
我在分而治之的算法上遇到了一点麻烦，正在寻找一些帮助。我试图编写一个名为sumArray的函数，它计算整数数组的和。 此函数必须通过将数组一分为二并对每一半执行递归调用来完成。我曾尝试使用类似的概念，当我编写递归和算法和分治算法来识别数组中的最大元素时，我使用了这些概念，但我很难将这两个想法结合起来。 下面是我为sumArray编写的代码，它编译，但没有返回正确的结果。
-
10.3 分治法 分治法（divide-and-conquer）是解决问题的一种常用策略，其思想是将难以处理的较大 问题分解为若干个较小的子问题，然后分别解决这些子问题，并从子问题的解构造出原问题 的解。“分”是指将原问题分解，“治”是指解决问题。 “分治”仅提及了分而治之的过程，而未提及此方法的另一个特点——递归。当我们将 大问题分解成子问题后，经常会发现子问题与大问题本质上是相同的问题，因此可