这种原位阵列反转的时间复杂度是多少？

小编典典

这种原位阵列反转的时间复杂度是多少？

algorithm

这个函数是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。

阅读 301

2020-07-28

共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表示法时很常见

2020-07-28