이항 계수는

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] 

을 기본적 재귀 공식을 사용하여 다음을(n, r-1)

이것은 2 차원 논리가 O (r) 복잡도를 갖는 반면, nr) 복잡성.

여기에 뭔가가 있습니까?

Answer 1

모든 값을 원한다면 2D 로직이 확실히 더 효율적입니다. 2D 로직은 예를 들어, 하드웨어 곱셈 및 나눗셈이 결여 된 몇몇 하드웨어상의 몇몇 파라미터들에 대해 더 효율적일 수있다. 나누기 전에 곱할 때 정수 오버플로에주의해야합니다. 반면 2D 반복의 정수 추가는 항상 좋습니다. 그 외에는 1D 재발이 더 좋습니다.