javascript - 递归遍历数组的大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 进行下一次递归调用，像循环一样逐步遍历数组，并在每个调用帧完成持续工作。

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