阶乘计算的时间复杂度是什么？（Big O）

Question

对于迭代版本，它是线性的：

// O(n)
function factorial (n) {
  let ret = 1;
  for(let i = 2; i <= n; i++) {
    ret = ret * i;
  }
  return ret;
}

递归版本似乎也是线性的：

function factorialR (n) {
  if( n === 0 || n === 1 ) {
    return 1;
  } else {
    return n * factorialR(n - 1);
  }
}

递归版本也是线性的吗？相比每次添加值的循环，它只是一个额外的函数调用。

- jennifer

---

你在函数中只针对每个数字传递一次，这是线性的。 - Nicolas

它们在大O表示法中都是线性的。如果考虑常数因素，你认为哪个更有效率？ - jennifer

鉴于后一个函数是尾递归的，编译器可能会将其优化为循环。因此，在效率方面，这是一个抉择。您可以使用 http://jsben.ch/ 这样的网站来比较这两个实现；我刚刚做了这件事，在 Chrome 中速度大致相同。 - benbotto

什么是尾递归？“尾”具体指的是什么？ - jennifer

简而言之，它只是意味着函数中的最后一个调用是对自身的调用。https://en.wikipedia.org/wiki/Tail_call 其中有一节关于将尾递归函数转换为循环的内容。 - benbotto

Answer 1

你的两个函数在时间复杂度上都是 O(n)。

第一个函数很简单明了。

第二个函数在每次迭代中调用递归函数一次，因此它的时间复杂度也是O(n)。

- technophyle

---

抱歉，不是那个意思，我是指将函数的推入/弹出存储器堆栈。 - technophyle

我认为这并不完全准确，@technophyle，快速基准测试将显示两者大致相等。尾递归很容易转换为循环，并且任何半吊子编译器都会优化尾递归。 - benbotto

是的，我的意思是几乎所有情况下都可以将递归函数优化为循环。从性能和内存使用方面来看。 - technophyle

总的来说，“循环迭代”比“函数迭代”更快，因为函数堆栈的原因，但这是学术上的问题，因为大多数编译器会优化成循环。 - jennifer

是的，我认为@j.a.说得很准确。但是要严谨一些，大多数编译器将优化尾递归，而不一定是递归。 - benbotto

Answer 2

如果您的算法是递归的，每个级别有b个递归调用，并且有L个级别，则该算法的复杂度大约为O(b^L)，但这只是一个粗略的上限。实际复杂度取决于每个级别执行哪些操作以及是否可以进行修剪。

来源：Stephen Halim

要了解更深入和复杂的递归时间复杂度，请访问此处。

- Abhishek Kumar