二項係数は

Question

動的プログラミングを使用して二項係数演算の

ほとんどの実装では、これらの例のように、2次元アレイを使用する： http://www.csl.mtu.edu/cs4321/www/Lectures/Lecture%2015%20-%20Dynamic%20Programming%20Binomial%20Coefficients.htm

http://www.geeksforgeeks.org/dynamic-programming-set-9-binomial-coefficient/

私の質問は、理由であります基本的に再帰式を使用して

def C(n, r): 
    memo = list() 
    if (r > int(n/2)): 
     r = n - r 
    memo.append(1.0) 
    for i in range(1,r+1): 
     now = ((n-i+1)*memo[i-1])/i 
     memo.append(now) 
    return memo[r] 

：ちょうどこのような1次元アレイを使用して計算しない（n、r-1）

これはO（r）の複雑さを持ち、2次元ロジックはO（r、 nr）複雑さ。

ここに何か不足していますか？

Answer 1

すべての値が必要な場合は、2Dロジックが確かに効率的です。 2Dロジックは、例えば、ハードウェアの乗算および除算がない、いくつかのハードウェア上のいくつかのパラメータに対してより効率的であり得る。分割する前に乗算するときは整数のオーバーフローに注意しなければなりませんが、2Dの繰り返しにおける整数の加算は常に問題ありません。それ以外は、1Dの再発が良いです。