[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 的详细介绍:请点这里
Python 的下载地址:请点这里