Acho que a ideia principal é aproveitar o fato de não precisar recalcular tudo todas as vezes.
Por exemplo, vamos supor que eu já calculei $3!$ usando um loop (multiplicando todos os inteiros de 1 a 3). Depois, quando for calcular $4!$, não preciso fazer todo o loop de 1 a 4. Eu posso fazer apenas $4\times 3!$ usando o resultado de $3!$ que já havia sido calculado anteriormente. E depois, se tiver um número maior (por exemplo, 8), eu posso multiplicar até o 5 ($8\times 7\times 6\times 5$) e depois multiplicar isso por $4!$ que já foi calculado.
Eu posso inclusive usar o próprio objeto final para isso. Pois ele está justamente armazenando os fatoriais que eu já calculei. Algo assim:
function fat(n, result) {
// caso haja números repetidos na entrada, não preciso recalcular
if (n in result) {
return;
}
var fat = n;
for (var i = n - 1; i > 1; i--) {
// se o fatorial de "i" já foi calculado, posso multiplicar direto e interromper o loop
if (i in result) {
// guarda o fatorial em result, que pode ser reusado em futuros cálculos
result[n] = fat * result[i];
return;
}
fat *= i;
}
result[n] = fat;
}
function calculeFactorial(...nums) {
var result = {};
for (var num of nums) {
fat(num, result);
}
return result;
}
console.log(calculeFactorial(3, 4, 5)); // { '3': 6, '4': 24, '5': 120 }
Assim só tem retrabalho quando os primeiros números são maiores. Por exemplo, se calcular primeiro $20!$, somente este valor ficará em result
. Depois, se tiver que calcular $4!$, não há resultado anterior calculado para reaproveitar, então vai ter que fazer o loop de 1 a 4.
Então outra forma seria pré-calcular todos os fatoriais até o maior dos números, e depois retornar apenas os que precisar:
function calculeFactorial(...nums) {
var maior = Math.max(...nums);
var fatoriais = [ 1 , 1 ]; // já começa com os fatoriais de 0 e 1 ("trapaça"?)
// assumindo que nunca terá números menores que 1
var fat = 1;
for (var i = 2; i <= maior; i++) {
fat *= i;
fatoriais[i] = fat; // já deixa pré-calculado todos
}
// depois pega só o que precisa
var result = {};
for (var n of nums) {
result[n] = fatoriais[n];
}
return result;
}
Por exemplo, se os números forem 3, 4 e 5, primeiro ele vai calcular todos os fatoriais até 5, que é o maior valor de todos. Afinal, uma hora vai precisar fazer o loop até 5, então eu faço apenas uma vez, e aproveito para ir guardando os resultados intermediários. No final, fatoriais
terá todos os fatoriais de 1 a 5.
Depois, basta pegar os fatoriais dos números que foram passados e retornar.
Fiz uns testes com o Benchmark.js e a primeira solução se mostrou mais rápida. Quando os primeiros números são maiores, a diferença diminui um pouco, por causa do que já foi dito (precisa recalcular os seguintes), mas ainda sim continua sendo mais rápida.
Que isso! Sensacional sua abordagem e análise, não tinha pensado em tantos detalhes assim. Com base em alguns pontos que você evidenciou, fiz algumas melhorias no meu código:
const calculeFactorial = (...numbers) => {
const factorials = {};
let factorial = BigInt(1);
for (const number of numbers) {
// para sequencias numéricas que possuem valores repetidos, evitamos
// recalcular o mesmo valor, checando se ele já foi calculado. Caso não, seguimos.
if (!(number in factorials)) {
// checa se o valor atual que será calculado, possui um antecessor já calculado.
// seguindo a lógica evidenciada por você: 4! = 4 * 3!
if (number - 1 in factorials) {
factorials[number] = BigInt(number) * factorials[number - 1];
continue;
}
for (let i = BigInt(number); i >= 1; i--) factorial *= i;
factorials[number] = factorial;
factorial = BigInt(1); // reseta a variável
}
}
return factorials;
};