很多朋友对于汉诺塔时间复杂度和汉诺塔n层公式不太懂，今天就由小编来为大家分享，希望可以帮助到大家，下面一起来看看吧！
本文目录
一、汉诺塔的复杂度是多少
汉诺塔问题的时间复杂度为O(2^n)。
时间复杂度的计算：用递归来解决汉诺塔问题是非常方便的选择。
设盘子个数为n时，需要T(n)步，把A柱子n-1个盘子移到B柱子，需要T(n-1)步，A柱子最后一个盘子移到C柱子一步，B柱子上n-1个盘子移到C柱子上T(n-1)步。
所以，汉诺塔问题的时间复杂度为O(2^n)。
递归算法所体现的“重复”一般有三个要求：
1、每次调用在规模上都有所缩小（通常是减半）。
2、相邻两次重复之间有紧密的联系，前一次要为后一次做准备(通常前一次的输出就作为后一次的输入)。
3、在问题的规模极小时必须用直接给出解答而不再进行递归调用，因而每次递归调用都是有条件的（以规模未达到直接解答的大小为条件），无条件递归调用将会成为死循环而不能正常结束。
二、汉诺塔问题的时间复杂度是多少
汉诺塔问题的时间复杂度为O(2^n)。
时间复杂度的计算：用递归来解决汉诺塔问题是非常方便的选择。
设盘子个数为n时，需要T(n)步，把A柱子n-1个盘子移到B柱子，需要T(n-1)步，A柱子最后一个盘子移到C柱子一步，B柱子上n-1个盘子移到C柱子上T(n-1)步。
所以，汉诺塔问题的时间复杂度为O(2^n)。
递归算法所体现的“重复”一般有三个要求：
1、每次调用在规模上都有所缩小（通常是减半）。
2、相邻两次重复之间有紧密的联系，前一次要为后一次做准备(通常前一次的输出就作为后一次的输入)。
3、在问题的规模极小时必须用直接给出解答而不再进行递归调用，因而每次递归调用都是有条件的（以规模未达到直接解答的大小为条件），无条件递归调用将会成为死循环而不能正常结束。
三、各种算法的时间复杂度
1、 O(1)< O(logn)< O(n)< O(nlogn)< O(n^2)< O(n^3)< O(2^n)< O(n!)< O(n^n)
2、一般时间复杂度到了2 n(指数阶)及更大的时间复杂度,这样的算法我们基本上不会用了,太不实用了.比如递归实现的汉诺塔问题算法就是O(2 n).
3、平方阶(n^2)的算法是勉强能用,而nlogn及更小的时间复杂度算法那就是非常高效的算法了啊.
4、冒泡排序,简单选择排序,堆排序,直接插入排序,希尔排序的空间复杂度为O(1),因为需要一个临时变量来交换元素位置,(另外遍历序列时自然少不了用一个变量来做索引)
5、快速排序空间复杂度为logn(因为递归调用了),归并排序空间复杂是O(n),需要一个大小为n的临时数组.
6、基数排序的空间复杂是O(n),桶排序的空间复杂度不确定
7、原文：
如果你还想了解更多这方面的信息，记得收藏关注本站。
