无法计算出此算法的运行时间

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

这里是python中alg的一个小例子，结果为false，但列表中有两个元素满足U L=k

def testArray(a, k):
    first = 0
    last = len(a) - 1

    while (first < last):
        print first, last
        if (a[first] + a[last] == k):
            return True
        elif (a[first] + a[last] < k):
            last=last-1
        else:
            first=first+1
    return False

a = [3, 1, 5, 3, 6]
print testArray(a, 6)

Answer 2

算法的运行时间是O（N），因为在最坏的情况下，您只需迭代整个数组。

虽然你的算法不能解决这个问题。例如，考虑{9,1,3,4,2}。在这种情况下，如果k为12，则返回false。对于您的算法，应该首先对输入数组进行排序，然后将其传递给算法，在最坏的情况下，算法将采用＜code＞O（NlogN）。

然而，更快的解决方案是使用类似于< code>HashMap的东西在< code>O(N)时间内解决问题。