구조적으로 다른 모든 이진 트리의 수를 계산하는 데 시간이 얼마나 걸릴까요? 상기 방법을 사용

Question

여기서 제시 : http://cslibrary.stanford.edu/110/BinaryTrees.html#java

 
12. countTrees() Solution (Java) 
/** 
For the key values 1...numKeys, how many structurally unique 
binary search trees are possible that store those keys? 

Strategy: consider that each value could be the root. 
Recursively find the size of the left and right subtrees. 
*/ 
public static int countTrees(int numKeys) { 
    if (numKeys <=1) { 
    return(1); 
    } 
    else { 
    // there will be one value at the root, with whatever remains 
    // on the left and right each forming their own subtrees. 
    // Iterate through all the values that could be the root... 
    int sum = 0; 
    int left, right, root; 

    for (root=1; root<=numKeys; root++) { 
     left = countTrees(root-1); 
     right = countTrees(numKeys - root); 

     // number of possible trees with this root == left*right 
     sum += left*right; 
    } 

    return(sum); 
    } 
} 

I 그것이 해당 될 수있는 감이 (N-1) (N-2) ... (1), 즉 N!

memoizer를 사용하는 경우 복잡도 O (n)입니까?

Answer 1

노드 수가 n 인 전체 이진 트리의 수는 카탈로니아의 n 번째 숫자입니다. 복잡도가 O (N) 인

카탈루냐어로 번호가 산출된다. 룩업 테이블에 얼마나 많은 히트

http://mathworld.wolfram.com/BinaryTree.html

http://en.wikipedia.org/wiki/Catalan_number#Applications_in_combinatorics

Answer 2

이 알고리즘이 주어진 노드 수인 에 대해 사용하는 countTrees 호를 계산하기에 충분합니다. 약간의 시운전이 끝나면 n> = 2 인 5 * 3^(n-2) 통화가 필요하며 n보다 훨씬 느리게 성장하는 것처럼 보입니다. 이 단언의 증거는 독자를위한 운동으로 남아있다. :-)

당신이 제안한대로 Oo (n) 통화가 필요합니다.

덧붙여 말하자면, n 개의 노드를 가진 이진 트리의 수는 n 번째 Catalan number과 같습니다. C _n을 계산하는 명백한 접근법은 모두 n에서 선형으로 보이므로 countTrees의 메모 구현이 가장 좋은 방법 일 수 있습니다.

Answer 3

확실하지가 (확실히 슈퍼 선형 및 함수 호출의 오버 헤드가되는)하기 위해가는 memoized 버전이지만,

int C=1; 
    for (int i=1; i<=n; i++) 
    { 
     C = (2*(2*(i-1)+1)*C/((i-1)+2)); 
    } 
    return C; 

참고 메모이 제이션 및 도표화 0 차이 : n 번째 카탈루냐어 번호와 동일하게 산출 한 결과를 수학적으로 증명 한 신속 선형 시간을 표 방법을 요리 할