汉诺塔有关问题与递归算法，时间复杂度
汉诺塔问题与递归算法，时间复杂度
伪代码：
HANOI(n, A, B, C)
1 if n = 1
2 then print A, "-->", C
3 return
4 HANOI(n - 1, A, C, B)
5 print A, "-->", C
6 HANOI(n -1, B, A, C)
n个盘子从A移到C。
书上分析运行时间时说，第4-6行说明对n > 1，T(n) = 2*T（n - 1）+ 1, 谁能跟我分析分析这个结论是怎么得出来的？
------解决方案--------------------
使用递归树来分析的，理论叫"Master Method"，在《算法导论》第三版的4.4节有详细的介绍
1、首先看函数的输入元素，规模是n个
2、然后函数内部开始递归，将原来规模是n的问题，分解成两个两个规模是n-1的子问题
3、每个规模是n-1的子问题又会递归分解成两个n-2的子问题，以此类推
4、于是就能够得出来结论 T(n) = 2T(n-1) + 1了。最后这个1是1,2,3,5这种语句的开销，是常量
伪代码：
HANOI(n, A, B, C)
1 if n = 1
2 then print A, "-->", C
3 return
4 HANOI(n - 1, A, C, B)
5 print A, "-->", C
6 HANOI(n -1, B, A, C)
n个盘子从A移到C。
书上分析运行时间时说，第4-6行说明对n > 1，T(n) = 2*T（n - 1）+ 1, 谁能跟我分析分析这个结论是怎么得出来的？
------解决方案--------------------
使用递归树来分析的，理论叫"Master Method"，在《算法导论》第三版的4.4节有详细的介绍
1、首先看函数的输入元素，规模是n个
2、然后函数内部开始递归，将原来规模是n的问题，分解成两个两个规模是n-1的子问题
3、每个规模是n-1的子问题又会递归分解成两个n-2的子问题，以此类推
4、于是就能够得出来结论 T(n) = 2T(n-1) + 1了。最后这个1是1,2,3,5这种语句的开销，是常量