手机版
你好,游客 登录 注册 搜索
背景:
阅读新闻

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

[日期:2014-07-23] 来源:Linux社区  作者:sikeIT [字体: ]

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

二叉树先序中序非递归算法 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.htm

Python脚本获取Linux系统信息 http://www.linuxidc.com/Linux/2013-08/88531.htm

Ubuntu下用Python搭建桌面算法交易研究环境 http://www.linuxidc.com/Linux/2013-11/92534.htm

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

本文永久更新链接地址http://www.linuxidc.com/Linux/2014-07/104547.htm

linux
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数

       

评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款