algorithm - 迭代 O(2^n) 算法的示例

Question

正如标题所说，什么是迭代 O(2^n) 算法的示例？通常什么时候发生？

标签： algorithmtime-complexity

Answer 1

河内塔就是一个很好的例子。

河内塔由三个杆或钉子组成，n 个圆盘一个接一个。

谜题的目的是按照这 3 条规则将整个堆栈移动到另一个杆。

1.一次只能移动一个磁盘。2.每次移动都包括从其中一个堆栈中取出上面的圆盘，并将其放在另一个堆栈的顶部或空棒上。3.较大的磁盘不能放在较小的磁盘上。

解决汉诺塔难题所需的最小移动次数为 2^n - 1，其中 n 是磁盘的数量。

https://en.wikipedia.org/wiki/Tower_of_Hanoi#Iterative_solution