阶乘计算的大 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)也是如此。