0

ncrこの投稿に出くわしたとき、私は可能な効率的な計算方法を読んでいました 。

nCr を計算するより良い方法はどれですか

ここで与えられた2番目の答えは、私には理解できません。コードは次のとおりです。

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;
}

そして、これの複雑さは何ですか？例でやってみたら正解が出たのですが、その条件は何ですか？

4

2 に答える 2

0

それは最適化の結果であり、計算します

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

最初 : アルゴリズムの最適化 : as C nk = C n (nk) : より少ない項を持つものを計算します - いいね。

次の計算の最適化: 計算ans * n / jを行うとき、操作を実行する前に分数を単純化しようとします - IMHO これは人間が行う方法であるため、非常に議論の余地があります (あなたと私はより速く計算します6 / 3が12345678 / 9)、プロセッサにとっては、この最適化は余分な操作を追加するだけです。

于 2014-10-03T07:56:11.403 に答える
0

リンクの状態のように、ループ内の複数の条件は、実行時にオーバーフローを処理すること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;

C(n , r) = n! / (nr)! ろ！ほとんどの要因は単純化できます。

複雑さはk.

于 2014-10-03T07:46:54.467 に答える