没有合适的资源?快使用搜索试试~ 我知道了~
首页数据结构系列:深度解析补偿分析法与自适应数据结构
数据结构系列:深度解析补偿分析法与自适应数据结构
需积分: 32 2 下载量 40 浏览量
更新于2024-07-22
收藏 736KB PDF 举报
本篇文章主要探讨了数据结构复杂性分析中的一个重要概念——补偿分析法,也称为均摊分析。这是一种在处理系列操作而非单一操作时的性能评估方法,特别是在数据结构的应用中,如自组织线性表和自适应树。例如,对于二进制计数器的加1操作,常规分析可能会得出单次操作的最坏情况时间复杂度为O(n),但如果考虑到操作之间的关联性,即每次操作都是基于前一次结果进行的,那么整个序列的性能不能简单地通过单次最坏情况相加得出。 具体来说,文章指出,如果每次加1都在前一次结果的基础上进行,如初始值为0000(n=4),每次操作会将最低位的1变为0,导致计数器向右移动。在这种情况下,虽然单次操作可能需要移动n次,但通过连续的“0”和“1”交替,可以形成周期性,使得复杂度不再线性增长。例如,从0000到0001只需一次变化,然后再次回到0000可能只需要一次,如此循环。通过这种补偿分析,我们能够更好地理解整个操作序列的平均性能,而不仅仅是最坏情况。 文章假设进行了总计2^n次操作,从00…00到11…11,通过分析每个阶段的变化,发现复杂度并非线性增加,而是呈现出一种更有效的模式。通过对所有操作复杂度的整体考虑,而不是简单累加,可以得到更准确的平均时间复杂度。这种方法对于理解和设计高效的数据结构至关重要,因为它揭示了在实际操作序列中,数据结构性能可能会好于单个操作的最坏情况预测。通过这种方式,研究者和开发者可以在设计和优化数据结构时,更加关注长期行为而非局部峰值。
资源详情
资源推荐
![](https://csdnimg.cn/release/download_crawler_static/8361811/bg10.jpg)
希赛,中国最大的 IT 资源平台
注:本文来源互联网,由希赛网下载频道整理发布,版权属于原作者
(Z 上没盘),可以先借助 Z(Z 上也没盘),把前 n-1 个盘(从 1
到 n-1 排列)从 X 移到 Y(Y 上没盘),然后把第 n 个盘从 X 移到 Z,
最后借助 X(X 上没盘)把前 n-1 个盘(从 1 到 n-1 排列)从 Y
移到 Z(Z 上有 n 号盘)。注意最后一步其实和原来问题不同了,但
是由于 Z 柱上的 n 号盘不被移动,且不影响前 n-1 个盘的移动,所
以仍然可以把它看成和原问题一样的问题。
上面说明时用了一大堆括号,主要原因是说话时总会漏掉一些
条件,而我们汉语又没有使用定语从句的语法(近代汉语的破折号
有类似的作用,但看起来也不太舒服)。从这点看英语比汉语要圆滑。
比如你说:“老子天下第一,谁也不怕……”,回头发现老婆站在身
后,笑呵呵的问你“是吗?”。 如果你反应快的话可能加上半句“除
了你之外”。不过即使这样,她也不会相信。因为虽然在现代汉语中
允许这种语法,但毕竟不太自然,而且又在这种语境之中。如果是
英文“I fear nobody except ……”是非常自然的,不这么说反而
不自然。不过汉语口语中也有类似的用的比较自然的。比如单田芳
讲评书经常使用的一招:某人被打败了,大叫“我不服……”,一
看刀架到脖子上了又冒出半句“也得服”。
闲话少说,书归正传。Method1 除了上面的解释方法,还有一
种。
把原问题看作使用最少的次数把 n 个盘借助 Y 从 X 移到 Z。移
动时除了不能大盘压小盘外没有任何限制。原问题分三步:首先用
最少的次数把 n-1 个盘借助 Z 从 X 移到 Y;把 n 号盘从 X 移到 Z;
![](https://csdnimg.cn/release/download_crawler_static/8361811/bg11.jpg)
希赛,中国最大的 IT 资源平台
注:本文来源互联网,由希赛网下载频道整理发布,版权属于原作者
最后用最少的次数把前 n-1 个盘借助 X 从 Y 移到 Z。为什么这样三
个步骤得到的就是 n 个盘移动的最少次数呢?因为要把 n 号盘移到
Z(不管是从 X 还是 Y)都至少要一次;移到 n 从 X(或 Y)到 Z 的
前提是前 n-1 个盘在 Y(X),Z 上没有任何盘。如果 n 盘是从 X 到
Z,说明前面已经把 n-1 个盘从 X 移到 Y 了,最少需要步骤一那么
多的移动。如果是从 Y 到 Z,说明前面已经把 n 号盘从 X 移到了 Y;
而把 X 移到 Y 说明前 n-1 个盘已经移到了 Z,移动前 n-1 个盘需
要至少步骤一那么多次数的移动。同理,任何正确的移动方法在把
n 号盘最后一次移到 Z 之后(可能有移到 Z 又移动走的情况,最后
一次移到 Z 后 n 号盘就不会再动了),要把前 n-1 个盘移到 Z 上面。
这 n-1 个盘的移动次数必须是最少的,否则整个过程就不是最少的
移动过程。
当然除了次数最少的移动方法外还有其它的方法,比如
public void Method4(int n,char X,char Y,char Z){
if(n==1)
MoveDisk(1,X,Z);
else{
Method4(n-1,X,Z,Y);
MoveDisk(n,X,Z);
MoveDisk(n,Z,X);
MoveDisk(n,X,Z);
![](https://csdnimg.cn/release/download_crawler_static/8361811/bg12.jpg)
希赛,中国最大的 IT 资源平台
注:本文来源互联网,由希赛网下载频道整理发布,版权属于原作者
Method4(n-1,Y,X,Z);
}
}
看起来似乎很无聊,把 n 号盘从 X 移动 Z 又移回到 X 又移回到
Z。你也可以把在第一步把 n-1 个盘从 X 移到 Y,然后又移到 X 最
后又移到 Y。不管怎么样,都是解决问题的一种方法。如果我们不
知道正确的解法的时候尝试移动时也可能移动后发现不对又移回去
的。
下面看一个不太无聊的解。问题和原来有点区别,除了不能大
盘压小盘外,还不能直接把盘从 X 移到 Z。即如果想把一个盘从 X
移到 Z,则要借助 Y,先把盘从 X 移到 Y,然后把盘从 Y 移到 Z。正
确的解法是:
public void Method3(int n,char X,char Y,char Z){
if(n==1){
if(Y=='y'){
MoveDisk(1,X,Y);
MoveDisk(1,Y,Z);
}
else
MoveDisk(1,X,Z);
}
![](https://csdnimg.cn/release/download_crawler_static/8361811/bg13.jpg)
希赛,中国最大的 IT 资源平台
注:本文来源互联网,由希赛网下载频道整理发布,版权属于原作者
else{
Method3(n-1,X,Y,Z);
MoveDisk(n,X,Y);
Method3(n-1,Z,Y,X);
MoveDisk(n,Y,Z);
Method3(n-1,X,Y,Z);
}
}
解释方法就省了。这个算法没有什么特别的地方,但我们发现
在递归的出口 n==1 的地方有些麻烦。因为 n==1 就是要把盘从
X 移到 Z,如果 Y==’y’,说明我们是要把盘从 x 移到 z,这是规
则不允许的,要借助 y。这么一来看起来程序不太美观。如果我们
把递归出口改成 n==0 回怎么样呢?也就是说把 1 个盘从 X 移到 Z
能不能套用递归
else{
Method3(n-1,X,Y,Z);
MoveDisk(n,X,Y);
Method3(n-1,Z,Y,X);
MoveDisk(n,Y,Z);
Method3(n-1,X,Y,Z);
}
呢?代入 n=1 得到:
![](https://csdnimg.cn/release/download_crawler_static/8361811/bg14.jpg)
希赛,中国最大的 IT 资源平台
注:本文来源互联网,由希赛网下载频道整理发布,版权属于原作者
else{
Method3(0,X,Y,Z);
MoveDisk(1,X,Y);
Method3(0,Z,Y,X);
MoveDisk(1,Y,Z);
Method3(0,X,Y,Z);
}
把 0 号盘(0 号盘在哪?)从某柱移到某柱是什么意思?我们
没办法移动不存在的盘,那只好什么也不干。则 else 里面变成:
MoveDisk(1,X,Y);
MoveDisk(1,Y,Z);
这正是把 1 号盘从 X 移到 Z 的办法。
所以修改一下:
public void Method2(int n,char X,char Y,char Z){
if(n==0)
return;
else{
Method2(n-1,X,Y,Z);
MoveDisk(n,X,Y);
Method2(n-1,Z,Y,X);
MoveDisk(n,Y,Z);
Method2(n-1,X,Y,Z);
剩余146页未读,继续阅读
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
sinat_25324833
- 粉丝: 0
- 资源: 1
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
最新资源
- AirKiss技术详解:无线传递信息与智能家居连接
- Hibernate主键生成策略详解
- 操作系统实验:位示图法管理磁盘空闲空间
- JSON详解:数据交换的主流格式
- Win7安装Ubuntu双系统详细指南
- FPGA内部结构与工作原理探索
- 信用评分模型解析:WOE、IV与ROC
- 使用LVS+Keepalived构建高可用负载均衡集群
- 微信小程序驱动餐饮与服装业创新转型:便捷管理与低成本优势
- 机器学习入门指南:从基础到进阶
- 解决Win7 IIS配置错误500.22与0x80070032
- SQL-DFS:优化HDFS小文件存储的解决方案
- Hadoop、Hbase、Spark环境部署与主机配置详解
- Kisso:加密会话Cookie实现的单点登录SSO
- OpenCV读取与拼接多幅图像教程
- QT实战:轻松生成与解析JSON数据
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)