algorithm - 无法计算出该算法的运行时间

Question

我被要求为这个问题编写算法:给定数组 A，我们想知道数组中是否有任意两个元素 U 和 L，且 U+L=K

我的算法是这样写的:

while(first<last)
{
  if(arr[first]+arr[last]==k)
     return true
  else if(arr[first]+arr[last]<k)
     last=last-1;
  else
     first++;
}
return false   

}

但问题是这个算法的运行时间是多少？是 O(nlogn) 吗？如果是，为什么？如果不是，我如何在 O(nlogn) 中实现它？

Answer 1

您的算法的运行时间是 O(N)，因为在最坏的情况下，您最终只会遍历整个数组。

尽管您的算法无法解决问题。例如考虑 {9,1,3,4,2}。在这种情况下，如果 k 为 12，它将返回 false。对于您的算法，应首先对输入数组进行排序，然后将其传递给算法，在最坏的情况下，这将花费 O(NlogN)。

不过，一个更快的解决方案是使用 HashMap 之类的东西在 O(N) 时间内解决问题。