二項係数の時間と空間の複雑さを計算するにはどうすればいいですか？ （繰り返し対反復）

Question

これは反復型ですが、再帰関数を呼び出します。それは時間/空間の複雑さに影響を及ぼしますか？

int factorial(int n) { 
    if (n == 1) { 
     return 1; 
    } 
    else { 
     return n * factorial(n - 1); 
    } 
} 

int binomial_coefficient_iterative(unsigned int n, unsigned int k) { 
    if (k == 0 || k == n) { 
     return 1; 
    } 
    else { 
     return (factorial(n)/(factorial(k) * factorial(n - k))); 
    } 
} 

これはC（N、K）= C（N-1、K）+ C（N-1、K-1）式を用いて計算再帰的バージョンです。

int binomial_coefficient_recursive(unsigned int n, unsigned int k){ 
    if (k == 0 || k == n) { 
     return 1; 
    } 
    else { 
     return binomial_coefficient_recursive(n - 1, k) + binomial_coefficient_recursive(n - 1, k - 1); 
    } 
} 

最後ではなく、少なくとも、あなたがC（N、K-1）を用いて二項係数C（N、k）を算出することができますか？

Answer 1

どちらの解決方法も再帰に依存します。第1版では、階乗の再帰呼び出しを簡単な繰り返しに置き換えることができます。

しかし、第2の解決策では、重複するサブ問題の再計算の問題があります。

C(n, k) = C(n-1, k) + C(n-1, k-1) 

あなたはそれがストア値を計算し、関数ではなく、計算、ルックアップ再同じparameteresで呼び出すときの値を返すされるたびにC（N、K）の値をキャッシュするメモ化を使用すべきです。

第1の問題では、階乗関数を複数回呼び出すと回避できます。戦略は、増分変化を計算することです。たとえば、factorial(k)を計算すると、

factorial(n) = factorial(k) * K+1 * K+2 ...n 

これにより、実行している乗算の回数が減ります。

問題の空間時間の複雑さに戻ります。

第一：それは

T(n,k) = T(n-1,k) + T(n-1,k-1) + O(1)   
    where T(n,n) = T(n,0) = O(1) 

になりますが、この差分方程式をします解く：

が2回目の複雑さは、あなたがN、KおよびNK乗算を行っている呼び出しここ3階乗用としてO（n）はT（n）= O（2^n）（フィボナッチシリーズの複雑さを見出すのに使用される同じ引数）

したがって、後の手法は指数関数的であり、メモを使用して呼び出すことができます。