javascript - 这个就地数组反转的时间复杂度是多少？

Question

这个函数的时间复杂度是O(n)还是O(log(n))。

function reverse(array) {
  for (var i = 0, j = array.length - 1; i < j; i++, j--) {
    var temp = array[i];
    array[i] = array[j];
    array[j] = temp;
  }

  return array;
}

乍一看，它似乎对输入进行了 n/2 次迭代。然而，如果你仔细想想，实际的低级操作数量接近于 2n。

Answer 1

所以假设你有一个长度为 n 的字符串然后你有指标i=0，和j = n-1循环一直持续到 i>=j，其中 j 减 1，i 加 1这将为您提供总共 n/2 次迭代。在循环内，您总共有 3 个语句，这意味着该循环将总共完成 3(n/2)。除此之外，您在循环外还有 1 个操作，留给我们

f(n) = 3(n/2)+1 which is O(n)

编辑:这假设循环维护操作(i++,j--)是微不足道的，这是处理 Big Oh 符号时的常见做法