divide et impera问题

Question

给定一个集合M，查找是否存在一对数字(a，b)，它们都属于M和a+b=x，其中x是先前指定的参数。这个问题应该用Divide et Impera in O(n * log )来解决。也许这个问题应该被分成两个一半大小的子问题，然后在O(n)中重新组合结果。

我想要一个给定问题的伪代码或解决它的提示。

Answer 1

不确定这是否符合您的要求，但是：

对集合进行除法和合并(此操作对集合的第一个和最后一个元素使用divide

• conquer).

• Start，并将它们的和与x进行比较。如果和相等，则完成。)如果和较大，则下到倒数第二个元素；如果和较小，则上到第二个element.

• Repeat步骤2，从排序集的末端到中心，直到找到求和到x的元素，或者没有更多的元素。

分治排序为O(n lg n)，遍历排序集的步长为O( n)，因此总复杂度为O(n lg N)。

埃德:求和到x，而不是M。

Answer 2

如果您对M(在O(n log n)中，使用D&I)进行排序，您可以在线性时间内检查是否有一个对具有正确的和。(提示:两个指针)。

如果您认为这不会算作D&I解决方案，您可以将检查步骤合并到排序的合并步骤中，如果找到匹配项，则提前退出。

附加:如果您在合并过程中进行检查，您最终将执行O(Doesn)个加法和比较步骤，而不是O(n)个步骤--但当然，这不会恶化渐近运行时，除了常数因子。