[Python]递归算法时间复杂度----汉诺塔

问题：汉诺塔递归算法时间复杂度二叉树先序中序非递归算法 http://www.linuxidc.com/Linux/2014-06/102935.htm递归算法转换为非递归算法 http://www.linuxidc.com/Linux/2014-06/102934.htm[Python]递归算法时间复杂度 http://www.linuxidc.com/Linux/2014-07/104546.htm算法如下：解释：size表示汉诺塔的规模，startStack表示汉诺塔起始，endStack 表示完成，midStack表示辅助 def Towers（size,startStack,endStack,midStack）: if size == 1: print "Move disk from ", firstStack, "to ", endStack else: Towers（size-1,firstStack,midStack,endStack） Towers（1,firstStack,endStack,midStack） Towers（size-1,midStack,endStack,firstStack）分析：问题规模设置为n，T（n）为问题规模所需步骤， T（n）=1+T（1）+2T（n-1）//规模为n-1时要经过两次，所以为2T（n-1）
=1+2+2T（n-1） //当规模为1时需要两步，因此为T（1）=2
=3+2[3+2T（n-2）] //规模为n-2时，重复上述操作 =9+4T（n-2） =9+4[3+2T（n-3）] =21+8T（n-3） ...... =C+2^kT（n-k）当n-k=1时，得到k=n-1， T（n）=C+2^（n-1）T（1）//其中T（1）=2 T（n）=C+2^n综上：汉诺塔时间复杂度为O（2^n）注：算法采用Python语言编写《Python核心编程第二版》.（Wesley J. Chun ）.[高清PDF中文版] http://www.linuxidc.com/Linux/2013-06/85425.htm《Python开发技术详解》.（周伟,宗杰）.[高清PDF扫描版+随书视频+代码] http://www.linuxidc.com/Linux/2013-11/92693.htmPython脚本获取Linux系统信息 http://www.linuxidc.com/Linux/2013-08/88531.htm在Ubuntu下用Python搭建桌面算法交易研究环境 http://www.linuxidc.com/Linux/2013-11/92534.htmPython 的详细介绍：请点这里
Python 的下载地址：请点这里本文永久更新链接地址：http://www.linuxidc.com/Linux/2014-07/104547.htm