javascript - 阶乘计算的大 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);
  }
}

递归版本也是线性的吗？而不是每个附加值的循环，它只是一个附加的函数调用。

Answer 1

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

第一个很简单。

第二个调用递归函数一次在每次迭代中，所以，它是 O(n)以及。