0

描述一个 O(n log n) 时间的算法，给定一个包含 n 个整数的集合S和另一个整数x ，确定S中是否存在两个元素之和正好为 x 的元素。

我计划为此使用二进制搜索。

ALGORITHM(S,x)
S=Insertion-Sort()
for i=1 to S.length
   n=x-S[i]
   if( Binary-Search(S,n) == true)
      return { S[i],n }


Binary-Search(A, v)
low=1
high=A.length

while low ≤ high
   mid=(low+high)/2

   if v = A[mid]
     return mid
   if v > A[mid]  
      low ← mid+1
   else
      high ← mid−1
 return NIL

我如何找到这个算法的时间复杂度？如果T(n)不是(n log n)，那么正确的算法是什么？

4

3 回答 3

3

算法的整体顺序由各个部分的最高顺序决定。您从插入排序开始，其最坏情况下的性能为 O(n^2)，因此您已经失败了。

如果您要用 O(n log n) 版本替换排序算法，那么您必须查看剩下的内容。您有一个长度为n的循环，其主体调用二进制搜索。正确编码的二进制搜索是 O(log n)，因此结果应该是 O(n log n)。添加两个 O(n log n) 进程仍然会给您留下 O(n log n)。

有另一种更快的方法来完成第二步，但我会留给你去发现。不会影响整体结果。

于 2013-08-27T16:45:31.393 回答
0

对于每个元素i：

  • 如果x-i在哈希表中，我们有我们的总和（i和x-i）
  • 插i入哈希表。

总运行时间 - O(n)。

于 2013-08-27T17:53:41.980 回答
0

正如其他答案指出的那样，您可以首先使用 O(n log n) 排序，然后在每个元素的 O(log n) 时间内搜索每个元素的补码，从而加起来为 O(n log n ） 全面的。

但是，我认为您也可以执行以下操作来获得 O(n) 算法。

请注意，如果两个数字的和为 x，则其中一个必须 >= x/2，另一个必须 <= x/2。因此，通过枢轴 x/2 将数组分成两部分，一个更大，一个更小。这需要 O(n) 时间。如果值 x/2 的元素不止一个，那么您就完成了。

现在为下部数组中x-i的所有元素构建一个哈希表。i这又需要 O(n) 时间。

现在在每次查找的恒定时间内搜索哈希表中高数组中的每个元素。因此，这也是 O(n)。

因此，整体复杂度 O(n)。

于 2013-08-27T17:27:21.713 回答