@Rufix

Как оптимизировать вычисление биномиального коэффициента?

Есть такая задача на codewars.
Грубо говоря необходимо написать формулу n! / (k! * (n - k)!).

На выходе я получил такой код:

function choose (n, k) {
  function factorial (i) {
    return (i > 0) ? i * factorial (i-1) : 1;
  }

  return factorial (n) / (factorial (k) * factorial(n-k));
  
}

Код рабочий. Но в конце этой каты написано следующее:

Будьте осторожны: ожидается определенная степень оптимизации, которая будет касаться как большей точности чисел (и их ошибок округления в таких языках, как JS), так и времени вычислений.

Я ничего не понял. О какой оптимизации идет речь и что вообще от меня хотят?
  • Вопрос задан
  • 621 просмотр
Решения вопроса 1
0xD34F
@0xD34F
function mul(start, end) {
  let result = 1;

  for (let i = start; i <= end; i++) {
    result *= i;
  }

  return result;
}

function choose(n, k) {
  return n > k
    ? Math.round(mul(n - k + 1, n) / mul(2, k))
    : +(n === k);
}
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
Morpheus_God
@Morpheus_God
Может идет речь о том, что на больших числах факториал обычно трудно вычислить через рекурсию.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы