問題:漢諾塔遞歸算法時間復雜度
二叉樹先序中序非遞歸算法 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 的下載地址:請點這裡