구함 : - 오더 이진 트리 출력 방법의 반복 화학식은

Question

가 I이 자바 메소드의 반복 화학식

void printInorder(Node<T> v) { 
    if(v != null) { 
     printInorder(v.getLeft()); 
     System.out.println(v.getData()); 
     printInorder(v.getRight()); 
    } 
} 

어떤 기준을 검색 잼의 비트에있어 : ​​

• 그 완전한 이진 트리가
• 나무가 노트와 O (N)의 복잡도 N을 가지고

(모든 내부 매듭은 모든 잎이 동일한 깊이, 2 명의 아이들이있다)

나는 n knots과 함께 나무의 depth h과 관련하여 반복 수식을 찾아야하며 추가 보너스로 O (n)에서 오는 공식을 외삽 할 필요가 있습니다.

지금이 내가 가진 것입니다 :

d = depth of the tree 
c = constant runtime for execution of the method itself 
d = 1: T(n) = c 
d = 3: T(n) = T(d=1) + T(d=2) + T(d=3) + c 

나는, 내가 어려움이 더이 분해 데 자신을 위해 일을 명확히하기 위해 예를 들어, D = 3을 사용했다. 제 가정은 정확합니까?

---

편집 : 일

[x] = { x in real numbers : max([x]) <= x }, [x] rounded down to next full number 
d = 1: T(d) = 1 
d > 1: T(d) = 2^(h-1) * T(n/(2^(h-1))) 

1: T(h) = T(i = 0) + T(i = 1) + ... T(i = h-1) 
2: T(h) <= (2^(0-1) + n/(2^(0-1))) + (2^(1-1) + n/(2^(1-1))) + ... + (2^(h-2) + n/(2^(h-2))) 
3: T(h) = n + n + ... + n 
4: T(h) = (h-1)n 
5: T(h) = O(n) 

트리의 깊이의 모든 수준은 정확히 2^(H-1) 노드가 포함되어 있기 때문에

에서 다음 시도, 4 호선의 시간 계수는 때문에 무시 될 수있다 n은 최종 결과와 더 관련이 있습니다.

Answer 1

T (N) = T (N/2) + T (N/2) + 1

• 등급 0 1 개 동작을 갖는다.

• 레벨 1에는 2 개의 연산이 있습니다.

• 레벨 2에는 4 개의 연산이 있습니다.

• 레벨 k는 2^k 연산을 갖는다.

• 나무의 깊이는 lgn입니다.

1 + 2 + ... + 2^LGN
= 2^0^2 + 1 + 2^2 + ... + 2^LGN =
(2^(LGN + 1) -1)/(2-1) = 2 * 2 * lgn =
2n.

Answer 2

여기서 이와 대신 지수로 표현 될 같은 점화식 허용 평활성 규칙 (레비 틴, 알고리즘의 설계 & 분석 2 판., 481-82)을 사용하는 다른 방법이다.

어느 접근법 - 앞뒤로 교체 -이 문제에 적합하다. 나는 소화하기 쉽도록 많은 경우에 역방향 치환을 발견한다.