Есть ли оптимизация для факторных расчетов?

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

Если вы не проводите исследования, интервьюер, вероятно, захочет проверить, как вы думаете.

Показывать итеративную и рекурсивную версию с объяснением Big O должно быть достаточно для начинающих.

Если вас попросят оптимизировать, укажите вариант использования и предложите, если применимо, памятку.

Если вас попросят оптимизировать, не запомнив, танцуйте курицу.

Answer 2

Да, есть способы сделать это, проверьте это: https://cs.stackexchange.com/questions/14456/factorial-algorithm-more-efficient-than-naive-multiplication http://www.luschny.de/math/factorial/FastFactorialFunctions.htm

Может потребоваться битовая манипуляция, что не очень рекомендуется в языки уровня хотя