递归遍历数组的大O算法

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) 吗？使用常量大 O 表示法？

Answer 1

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

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

这是 O(n)，因为算法访问每个元素一次，T(n) = T(n - 1) + 1。每帧可能有 1 次递归调用，它使用 i + 1 进行下一次递归调用，像循环一样逐步遍历数组，并在每个调用帧完成持续的工作。

顺便说一句，这是一个相当愚蠢的递归编写算法，因为问题 space 每次调用都没有被分解太多。如果数组足够大并且函数调用会产生大量开销（至少在没有尾调用优化的语言实现中，这有效地将递归调用后没有计算的递归转换为循环），您可以轻松地炸毁堆栈。更不用说，代码并不比循环更容易理解。对于对数堆栈深度的问题，最好使用递归，而不是线性的，除非问题非常小并且递归树很宽（例如指数），这占主导地位。

Answer 2

递归函数通常总是每圈调用一次，但这并不意味着它们是 O(1)。举个例子：

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

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

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

另一件需要考虑的事情是，在递归向下一步之后，调用函数可能无法 return，因为它正在等待被调用函数提出一些东西。只有当被调用函数到达终止条件时才会发生这种情况。在那之前，所有调用函数都会保留。因此，考虑递归复杂性的另一种方法是考虑需要调用多少函数，直到递归解决。

递归遍历数组的大O算法

Big O of algorithm that steps over array recursively

javascript

algorithm

recursion

big-o

time-complexity