0

我有一个相当困难的问题（甚至可能是一个 NP 难题 ^^），在大量结果中寻找解决方案。也许有一个算法。

下面的练习是人为的，但它是一个很好的例子来说明我的问题。

有一个带有整数的大数组。可以说它有 100.000 个元素。

int numbers[] = {-123,32,4,-234564,23,5,....}

我想以一种相对快速的方式检查这个数组中任何两个数字的总和是否等于 0。换句话说，如果数组有“-123”，我想查找是否还有一个“123”数字。

最简单的解决方案是蛮力 - 检查一切。这给了 100.000 x 100.000 一个很大的数字 ;-) 显然蛮力方法可以通过优化。订单号并仅检查负数和正数。我的问题是 - 有没有比优化蛮力更好的方法来找到解决方案？

4

4 回答 4

4

首先，按值的大小对数组进行排序。

然后，如果数据包含满足您所追求的条件的一对，则它包含数组中相邻的这样一对。因此，只需扫描寻找总和为 0 的相邻对。

总体时间复杂度是O(n log n)排序，O(n)如果你使用“作弊”排序而不是仅仅基于比较。显然，它不能在少于线性的时间内完成，因为在最坏的情况下，如果不查看所有元素，您将无法完成。我认为n log n在计算的决策树模型中可能是最优的，但这只是因为它“感觉有点像”元素唯一性问题。

替代方法：

一次将一个元素添加到基于哈希或基于树的容器中。在添加每个元素之前，检查它的负数是否存在。如果是这样，请停止。

在有很多合适对的情况下，这可能会更快，因为您节省了对整个数据进行排序的成本。也就是说，只要数据的任何子集处于其最终顺序，您就可以编写一个修改后的排序，通过检查相邻对来提前退出，但这是努力。

于 2012-10-10T16:16:31.257 回答
3

蛮力将是一个O(n^2)解决方案。你当然可以做得更好。

从我的头顶上，首先排序它。堆排序的复杂度为O(nlogn).

现在，对于第一个元素，比如说a，你知道你需要找到一个元素b，比如a+b = 0。这可以使用二进制搜索找到（因为您的数组现在已排序）。二分查找的复杂度为O(logn).

O(nlogn)这为您提供了复杂性的整体解决方案。

于 2012-10-10T16:16:49.597 回答
2

您提供的示例可以及时蛮力解决O(n^2)。

您可以开始将数字 ( O(n·logn)) 从小到大排序。如果您将一个指针放在开头（“最负数”）和另一个指针在末尾（“最正数”），您可以O(n)按照以下过程在附加步骤中检查是否存在这样的一对数字：

  • 如果两个指针处的数字具有相同的模块，则您有解决方案
  • 如果不是，则将模块较大的数字的指针移向“零”（即，如果是负侧的指针，则增加，如果是正侧的指针，则减少）
  • 重复直到找到解决方案，或者指针交叉。

总复杂度为O(n·logn)+O(n) = O(n·logn)。

于 2012-10-10T16:22:40.230 回答
0

使用 对数组进行排序Quicksort。发生这种情况后，使用两个索引，我们称它们为positive和negative。

positive <- 0
negative <- size - 1

while ((array[positive] > 0) and (array(negative < 0) and (positive >= 0) and (negative < size)) do
    delta <- array[positive] + array[negative]
    if (delta = 0) then
        return true
    else if (delta < 0) then
        negative <- negative + 1
    else
        positive <- positive - 1
    end if
end while
return (array[positive] * array[negative] = 0)

你没有说如果 0 是数组的一部分，算法应该做什么，我假设在这种情况下应该返回 true 。

于 2012-10-10T16:26:46.057 回答