阶乘计算有什么优化吗？

Question

线性时间复杂度的迭代和递归版本运行。有什么可以优化的吗？

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

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

Answer 1

是的，有办法做到看一下这个： https://cs.stackexchange.com/questions/14456/factorial-algorithm-more-efficient-than-naive-multiplication http://www.luschny.de/math/factorial/FastFactorialFunctions.htm

可能需要位操作，但在高级语言中并不完全鼓励

Answer 2

除非你在做研究，否则面试官可能会想测试你的思维方式。

显示迭代和递归版本以及大 O 的解释对于初学者来说应该足够了。

如果要求优化，请使用用例进行限定并建议记忆（如果适用）。

如果要求在没有记忆的情况下进行优化，请跳小鸡舞。

阶乘计算有什么优化吗？

Are there any optimizations to factorial calculations?

javascript

complexity-theory