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

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--）是微不足道的，这是处理大哦符号时的常见做法