第7章 时空权衡_第1页
第7章 时空权衡_第2页
第7章 时空权衡_第3页
第7章 时空权衡_第4页
第7章 时空权衡_第5页
已阅读5页，还剩22页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、时空权衡2什 么 是 时 空 权 衡 ？3时空权衡是指在算法的设计中，对算法的时间和空间作出权衡。通常使用额外的存储空间来实现更快或更方便的数据存取。 4常见的以空间换取时间的方法输入增强对问题的部分或全部输入做预处理,然后对得到的额外信息进行存储,以加速后面问题的求解。例如：计数排序，串匹配算法的改进预构造使用额外的存储空间来实现更快或更方便的数据存取散列法，B树5目 录目录节节Boyer-Moore算法Horspool算法计数排序节6计数排序 对待排序列表中的每一个元素，算出列表中小于该元素的元素个数，并把结果记录在一张表中。显然地，这个“个数”指出了该元素在有序列表中的位置。排序时只需简

2、单地把列表中的元素复制到新列表中的相应位置上。7计数排序8计数排序9计数排序l 算法效率 l 实际应用时，计数排序法很少用到但是，在一种情况下还是卓有成效的，即待排序元素的值都来自一个已知的小集合。例如：仅包含1，22) 1(1)(2011 nnnCninij10计数排序 计数排序法的一个应用是分布计数如果元素的值是来自位于l,u之间的整数，我们可以计算出这些值出现的频率，然后把它们存在数组F0.u-l中。然后把有序列表的前F0个位置填l，接下来的F1个位置填入l+1.11计数排序12计数排序13计数排序14H o r s p o o l 算 法Horspool算法和下面要讲到的Boyer-M

3、oore算法都是用到了，串匹配中的输入增强思想，对模式进行预处理，得到它的一些信息，然后在查找的过程中使用这些信息。15H o r s p o o l 算 法16H o r s p o o l 算 法17H o r s p o o l 算 法18H o r s p o o l 算 法19H o r s p o o l 算 法20H o r s p o o l 算 法如果在遇到一个不匹配字符之前，如果已经有k(0k0个成功匹配的字符所确定。称为好后缀移动好后缀移动把模式的结尾部分叫做模式的长度为k的后缀，记作suff(k)情况1：当模式中存在两个以上suff(k)的情况时，移动距离d2就是从第一个后缀的最右元素位置数到第二个suff(k) 最右边的距离。23Boyer-moore算法情况2：当模式中存在1个suff(k)的情况时24Boyer-moore算法为了避免情况2的出现，我们需要找出长度为lk的最长前缀，它能够和长度同样为l的后缀完全匹配。如果存在这样的前缀，我们通过求出这样的前缀和后缀之间的距离来作为移动距离d2的值，否则移动距离就是m25Boyer-moore算法开始结束构造失配移位表构造匹配移位表模式串与文本串左对齐模式串右端开始比较匹配成功到达文本末端模式串右移 d位发生失配NNYY26计数排序在一个由英文字母和空格构成的文本

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论