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

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。

- Eric Rini

---

n/2和2n都不是O(log(n))。 - user2357112

它仍然是O(n)。(它随着n的增长而线性增长) - Nina Scholz

它是“o(n/2)”。 - Mahi

你想要实现什么目标？ - guest271314

我正在尝试理解如何分析这个函数的时间复杂度，以一种适用于其他函数和循环的方式。 - Eric Rini

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

- Garrigan Stafford

---

嗯，我们为什么要假设 i++ (或 i = i - 1) 是“微不足道”的，但 data [i] = data [j] 却有“代价”。这个解释对我来说仍然没有意义。 - Eric Rini

只要这些操作每次花费的时间相同，它们需要多长时间并不重要。这就是我们在这里所说的“琐碎”的意思。如果您选择包括循环操作的成本，它只会改变常数因子（3、/2和+1），根据定义，这对最终答案没有影响。 - Logan R. Kearsley