使用O(logn)时间复杂度计算数组之和 [英] Calculating sum of array using O(logn) time complexity

问题描述

我有一个 n 个字符的数组.为了计算数组的总和，我使用了以下代码片段:

I have an array of n characters. To calculate the sum of the array I have used the following code snippet:

  var arr = [1,2,3,4,5,6]
  var i = 0;
  var j = arr.length - 1;
  var sum = 0;
  while(i<j || i==j){
     sum = sum + ((i==j) ? arr[i] : arr[i] + arr[j])
     i++;
     j--;
  }

我使用了两个指针 i 和 j 从两个方向遍历数组，并找到了总和.我想知道这是否是正确的方法，它是否以O(log n)时间复杂度运行?

I have used two pointers i and j to traverse the array from both directions and it finds the sum. I wanted to know whether this is a correct approach and does it run in O(log n) time complexity?

谢谢

推荐答案

虽然看起来算法的复杂度小于 O(N)，但实际上仍然是O(N).由于您仅以1为因数递增/递减，因此循环中的迭代次数约为 N/2 ，即 O(N).

Although it may seem like the complexity of your algorithm is less than O(N), it is actually still is O(N). Since you are only incrementing/decrementing by a factor of 1, the number of iterations in your loop would be about N / 2 which is O(N).

如果在每次迭代后都忽略N的一半，则将获得 O(log N)的时间复杂度，如二进制搜索算法所示.

You would achieve O(log N) time complexity if you disregarded half of N after each iteration as shown in an algorithm like binary search.

对于这个求和问题，您实际上可以通过使用数学方法在 O(1)时间内解决.请参阅:此Wikipedia页面.

For this summation problem, you can actually solve in O(1) time by using math. See: this wikipedia page.

您只能使用1到N的数学

you can only use math for 1 to N

这篇关于使用O(logn)时间复杂度计算数组之和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！