Hanoi塔问题的时间复杂性 Hanoi塔问题的时间复杂性为O(2n) ■证明:对n归纳证明移动次数move(n)=2n-1。 ■归纳基础:当n=1,move(1)=1=21-1 ■归纳假设:当n≤k,move(n)=2n-1 ■归纳步骤:当n=k+1,移动次数为 move(k+1)=2move(k)+1=2(2k-1)+1 2 k+1 由归纳法可知对任意的n有move(n)=2n-1 2021/221 计算机算法设计与分析 52021/2/21 计算机算法设计与分析 5 Hanoi塔问题的时间复杂性 ◼ Hanoi塔问题的时间复杂性为O(2n )。 ◼ 证明：对n归纳证明移动次数move(n) = 2n – 1。 ◼ 归纳基础：当n = 1， move(1) = 1 = 2 1 – 1。 ◼ 归纳假设：当n  k， move(n) = 2 n – 1。 ◼ 归纳步骤：当n= k + 1，移动次数为 ◼ move(k+1) = 2(move(k)) + 1 = 2(2k – 1) + 1 = 2k+1 – 1 ◼ 由归纳法可知对任意的n有move(n) = 2n – 1