Объяснение для расчета ncr

Question

Я читал возможные эффективные методы расчета ncr, когда я наткнулся на это сообщение.

Which is better way to calculate nCr

Второй ответ дается здесь, я не в состоянии понять, что. Код:

long long combi(int n,int k) 
{ 
    long long ans=1; 
    k=k>n-k?n-k:k; 
    int j=1; 
    for(;j<=k;j++,n--) 
    { 
     if(n%j==0) 
     { 
      ans*=n/j; 
     }else 
     if(ans%j==0) 
     { 
      ans=ans/j*n; 
     }else 
     { 
      ans=(ans*n)/j; 
     } 
    } 
    return ans; 
} 

И какая будет сложность для этого? Я попытался сделать это с примером, и ответ выходит правильно, но каковы эти условия?

Answer 1

, что это просто результат оптимизаций, он вычисляет

n!/k! (n-k)! = n * (n-1) * ... (n - k + 1)/k * (k-1) * ... * 1 

Первая: алгоритмическая оптимизация: как С п к = С п (п-к): вычислить ту, которая имеет меньше условия - хороший.

Следующих вычисления оптимизаций: при вычислении ans * n/j попытки упростить дробь перед выполнением операции - ИМХО это один весьма discutable, потому что это то, как человек будет делать (вы и я вычисляю быстрее 6/3 чем 12345678/9) но для процессора, эта оптимизация просто добавляет лишнюю операцию.

Answer 2

Как состояние в ссылке, множественное условие в цикле должно обрабатывать переполнение при выполнении ans = (ans * n)/j.

Так функция:

long long ans = 1; 
k = std::min(k, n-k); 
int j = 1; 
for (; j <= k; j++, n--) { 
    ans = (ans * n)/j; 
} 
return ans; 

Мы имеем С (п, г) = п!/(n-r)! р!, и большинство факторов можно упростить.

И сложность k.