两个整数数组中的总和等于ķ [英] Sum of two integers in an array equals K

问题描述

我看了查找数组中的两个元件总和为k 和<一href="http://stackoverflow.com/questions/8373614/how-can-i-find-two-elements-in-an-array-that-sum-to-k">How我能找到一个数组中两个元素的总和为k 因为它们是相关的。

I read Find two elements in an array that sum to k and How can I find two elements in an array that sum to k as they are related.

我知道一个O（n）的解决方案，但我看到了一个为O（n LOGN）也存在： -

I know a O(n) solution but i see that a O(n logn) also exists :-

p=0,q=n-1;
while(p<q)
{
  if(a[p]+a[q]==k)
  {
      cout<<a[p]<<"\t"<<a[q];
      p++;
      q--;
   }
   else if(a[p]+a[q]>k)
      q--;
   else 
      p++;
}

这需要事先排好序的数组。但由于p和q的值取决于该数组中的元素，我们怎么断言，这种算法的复杂度为O（n log n）的？

This requires the array to be first sorted. But since the values of p and q are dependent on the elements in the array, how do we assert that the complexity of this algorithm is O(n Log n)?

推荐答案

在一个有效的排序算法的复杂度为为O（n log n）的。

The complexity of an efficient sorting algorithm is O(n log n).

用什么样的 P 和①的变化，，而循环会遍历数组一次中的所有元素，因此它的复杂性 O（N）。

No matter in what way the p and q changes, the while cycle will iterate through all the elements in the array once, thus it's complexity is O(n).

添加两人在一起：为O（n log n）的+ O（N）= O（N日志N + N）=为O（n log n）的，因为n大于小得多ñ日志N ，当 N 是一个大数目。

Adding the two together: O(n log n) + O(n) = O(n log n + n) = O(n log n), because n is much smaller than n log n, when n is a big number.

这篇关于两个整数数组中的总和等于ķ的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！