如何设计具有时间复杂度O(n log )的搜索算法？

Question

描述一个O(n log )-time算法，该算法在给定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)，那么正确的算法是什么？

Answer 1

算法的整体顺序是由各个片段的最高阶所决定的。首先是插入排序，它的最坏的性能是O(n^2)已经失败了。

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

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

Answer 2

正如其他答案所指出的那样，您可以首先使用O(n log )排序，然后在O(log )时间内搜索每个元素的补码，从而使整个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)。

Answer 3

对于每个元素i

• 如果x-i在哈希表中，则有我们的和(i和x-i)。
• 将i插入哈希表中。

总运行时间- O(n)。