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

Question

Describe a O(n log n)-time algorithm that, given a set S of n integers and another integer x, determines whether or not there exist two elements in S whose sum is exactly 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

算法的整体顺序由各个部分的最高顺序决定。您从插入排序开始，其 worst-case performance is O(n^2)所以你已经失败了。

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

执行第二步还有另一种更快的方法，但我会将其留给您去发现。它不会影响整体结果。