欧卡2中文社区

 找回密码
 立即注册

QQ登录

只需一步,快速开始

需要三步,才能开始

只需两步,慢速开始

查看: 8412|回复: 1
收起左侧

[编程] 汉诺塔算法的复杂度是如何推导的?

[复制链接]
丶纠结灬 发表于 2021-7-21 05:30 | 显示全部楼层 |阅读模式
为什么是 2n
 楼主| 丶纠结灬 发表于 2021-7-21 06:32 | 显示全部楼层
设移动 n 个需要时间 T(n),首先需要借助 C 将 上面 n1 个圆盘移动到 B 上面,相当于 n-1 个圆盘借助B移动到C,因此此步骤需要时间 T(n1),然后将第 n 个圆盘移动到 C,需要时间为 1,然后在借助 A 将 B 上的圆盘移动到C,又是一个 T(n1),因此:
T(n)=2T(n1)+1

可以看出,每增加一个圆盘,所需时间翻倍,即复杂度为 2n

推导:
由于 T(1)=1 ,即一个圆盘时只需要移动一次,代入上面的公式,可得
T(2)=2+1=21+211T(3)=22+221...T(n)=2n1+2n11=2n1


所以
T(n)=2n1= O(2n)
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

客服QQ936487697|联系我们|手机版|欧卡2中国 ( 湘ICP备11020288号-1 )

GMT+8, 2025-4-4 14:19 , Processed in 0.053694 second(s), 11 queries , Redis On.

Powered by Discuz! X3.4

Copyright © 2001-2023, Tencent Cloud.

快速回复 返回顶部 返回列表