这种就地阵列反转的时间复杂度是多少？ [英] What is the time complexity of this in-place array reversal?

问题描述

这个函数是O（n）还是O（log（n））时间复杂度。

Is this function O(n) or O(log(n)) time complexity.

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。

At first glance it appears to be making n/2 iterations over the input. However, if you think about it, the actual number of lower level operations is closer to 2n.

推荐答案

所以假设你有一个字符串长度 n
然后你有指标 i = 0 和 j = n-1
循环继续，直到 i> = j ， j 递减1和 i 递增1
这将为您提供总计 n / 2 次迭代。
在循环中你总共有3个语句，这意味着循环将完成总计 3（n / 2）。除此之外，你在循环之外有1次操作，只剩下

So assume you have a string of length n Then you have indicators i=0, and j = n-1 The loop continues until i>=j with j decrements by 1 and i increments by 1 This will give you a total of n/2 iterations. Inside the loop you have a total 3 statements meaning the loop will complete a total of 3(n/2). Along with that you have 1 operation outside the loop leaving us with

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

编辑：这假设循环维护操作（ i ++ ， j - ）在处理Big Oh表示法时很常见

This assumes that the loop maintaining operations(i++,j--) are trivial which is common practice when dealing with Big Oh notation

这篇关于这种就地阵列反转的时间复杂度是多少？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！