되풀이 관계 트리 방법

Question

현재 재귀 항목을 파악하는 데 문제가 있습니다. 중간 단계가 있으므로 곧 작동하는 방법에 대한 설명과 도움을받을 수 있습니다.

그래서 나는 기본적으로 내가 관계를 (솔직히 ... 내가 확실하지 않다하는)는 T해야 작성하는 방법을 이해 하노이

TOWER_OF_HANOI (n, FirstRod, SecondRod, ThirdRod) 
    if n == 1 
      move disk from FirstRod to ThirdRod 
    else 
      TOWER_OF_HANOI(n-1, FirstRod, ThirdRod, SecondRod) 
       move disk from FirstRod to ThirdRod 
       TOWER_OF_HANOI(n-1, SecondRod, FirstRod, ThirdRod) 

의 타워를 해결하기위한 의사를 가지고 제공 (n) = 2T (n-1) + Ɵ (n), 맞습니까? 일종의 하위 문제가있는 트리를 만드는 방법을 일종의 이해하지만, 그렇다고해도 Ɵ (n) 또는 Ɵ (n log n) 또는 기타 등등의 최종 솔루션을 제공하는 프로세스를 완전히 이해하지는 못합니다.

어떤 도움을 주셔서 감사합니다.

Answer 1

1. 시간 복잡도는 T (n)이되었다고 가정이 가정된다 : T (N) = T (N-1) + T (N-1) + 1 = 2T (N-1) + 1. "+1"하지만 "+ n"이 아닌 이유는 무엇입니까? "FirstRod에서 ThirdRod로 디스크 이동"은 한 번의 이동으로 비용이 발생합니다. T (n)에 대한

2. = 2T (N-1) + 1, 정확히 같은 모양의 재귀 트리 : https://www.quora.com/What-is-the-complexity-of-T-n-2T-n-1-+-C C는 상수 (. 당신은, 이미지가 깔끔한 것이 도움이 될 수있는); 이는 작업 당 비용을 의미합니다. 하노이 타워의 경우, C = 1

3. 각 레벨의 비용 합계를 계산하면,이 경우에 쉽게 알 수 있습니다. 총 비용은 2^n-1이 될 것입니다. 비싼). 그러므로이 재귀 방정식의 답은 Ɵ (2^n)입니다.