递归遍历数组的算法的时间复杂度是什么？

Question

我有这个算法：

function f(arr, i, n) {
  if (i == n - 1) {
    return arr[i];
  }
  if (i == 0) {
    return (arr[i] + f(arr, i + 1, n)) / n;
  } else {
    return arr[i] + f(arr, i + 1, n);
  }
}

这是一种递归算法，但每次迭代只会调用一次。

我认为这可能是一个O(1^n)符号的算法，但如果是这样的话，

(1 ^ 1) = 1 (1 ^ 2) = 1 (1 ^ 3) = 1

那么它不就是O(1)吗？具有常数时间复杂度的Big O符号表示法？

- Giuliana Olmos

Answer 1

在考虑时间复杂度之前，先问自己：这个算法到底在做什么？这个问题可以帮助你建立对分析的直觉。在这种情况下，我们需要对一组数字取平均值。

其次，什么是O(1)？这意味着无论数组有多大，算法运行的时间都相同。因此，你的分析基本上是在说，在包含15个元素的数组和包含2000万个元素的数组中取平均值需要的时间是一样的。所以这里有些问题。

这是O(n)，因为算法访问每个元素一次，T(n) = T(n - 1) + 1。每个框架只可能有一个递归调用，并使用i+1来进行下一个递归调用，就像循环一样遍历数组，并在每个调用框架中执行恒定的工作。

顺便说一句，这是一个非常愚蠢的递归算法，因为每个调用并没有将问题空间分解得很小。如果数组足够大，并且函数调用产生了很多开销（至少在没有尾递归优化的语言实现中，尾递归优化将递归转换成循环），那么容易溢出堆栈。更不用说，代码并不比循环更容易理解。除非问题很小且递归树很宽（例如指数级），否则请优先考虑具有对数堆栈深度的问题而不是线性，这会主导时间复杂度。

- ggorlen

---

同意：看起来代码返回 arr[0] + (arr[1]到arr[n]之和除以n)，所以递归访问数组n次，因此是O(n)。 但像上面的答案一样，这是一个线性复杂度任务的递归解决方案。因此，如果使用简单的数组计算，而不是递归，效果可能会更好，甚至更好。 - wasiqam

Answer 2

递归函数通常每一轮只调用一次，但这并不意味着它们的时间复杂度是O(1)。看一个例子：

function recursive(n) {
  return recursive(n + 1)
}

这将无限运行。它应该具有O(∞)的复杂度，O(1)的复杂度根本没有意义，因为它根本没有帮助。

对于递归函数，您必须问自己，它需要多长时间才能终止，就像普通函数一样。

另一个要考虑的问题是，在递归下降一步之后，调用函数可能还不能返回，因为它正在等待被调用的函数提供一些东西。只有在调用的函数到达终止条件时才会发生这种情况。在那之前，所有调用函数都会留下来。因此，递归中考虑复杂性的另一种方式是考虑需要调用多少个函数，直到递归解析。

- Moritz Vetter

---

欢迎来到SO！对于不依赖于n的无限循环的时间复杂度有些争议和抽象 - 我建议添加一个基本情况，以使其保持在通常讨论的大O有限领域内。其次，“调用函数可能还不能返回...”并不是一种可靠的推断复杂性的方式。正如我的帖子所指出的那样，您可以拥有一个广泛的调用树，只在堆栈上保留少数几个函数，但执行指数级的工作。TCO可以使用仅1个调用运行O(n)算法。这个备注更多地涉及空间复杂度。 - ggorlen