使用 O(logn) 时间复杂度计算数组的总和

Question

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

  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)？

谢谢

Answer 1

虽然看起来你的算法复杂度小于 O(N)，但实际上仍然是 O(N)。由于您只有 incrementing/decrementing 的 1 倍，因此循环中的迭代次数约为 N / 2，即 O(N).

如果您在每次迭代后忽略 N 的一半，您将达到 O(log N) 时间复杂度，如二进制搜索等算法所示。

对于这道求和题，你实际上可以用数学在 O(1) 时间内解决。参见：this wikipedia page.

编辑：您只能将数学用于 1 到 N

使用 O(logn) 时间复杂度计算数组的总和

Calculating sum of array using O(logn) time complexity

javascript

arrays

big-o

time-complexity

data-structures