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

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

问题：汉诺塔递归算法时间复杂度

二叉树先序中序非递归算法

递归算法转换为非递归算法

[Python]递归算法时间复杂度

算法如下：

        解释：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中文版]

《Python开发技术详解》.( 周伟,宗杰).[高清PDF扫描版+随书视频+代码]

Python脚本获取Linux系统信息

在Ubuntu下用Python搭建桌面算法交易研究环境

Python 的详细介绍：请点这里
Python 的下载地址：请点这里

本文永久更新链接地址：