2010-2011-2《算法分析》ppt-6时空均衡_第1页
2010-2011-2《算法分析》ppt-6时空均衡_第2页
2010-2011-2《算法分析》ppt-6时空均衡_第3页
2010-2011-2《算法分析》ppt-6时空均衡_第4页
2010-2011-2《算法分析》ppt-6时空均衡_第5页
已阅读5页，还剩25页未读， 继续免费阅读

下载本文档

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

文档简介

1、时空平衡，基本理念，处理输入节省时间，处理存储结构节省时间。相应的问题：计数排序，字符串匹配哈希方法，B树作为索引，先看例子，例1斐波纳契数列无穷级数1，1，2，3，5，8，13，21，34，55，称为斐波纳契数列。它可以递归地定义为：边界条件、递归方程、例1中的斐波那契数列，并且第n个斐波那契数可以递归地计算如下：如果(n=1)返回1，则整数斐波那契数(整数n)；返回斐波那契(n-1)斐波那契(n-2)；时间复杂度：0(2n)空间复杂度：示例1 Fibonacci序列，非递归算法：int fibonacci(int n) int k，x，y，z；如果(n=1)返回1；x=1；y=1；对于(k

2、=1；k=n；k)z=x y；x=y。y=z。返回z；时间复杂度：O(n)空间复杂度：O(1)，示例2整数划分问题，q(10，10)？q(10，10)=1 q(10，9)=1 q(10，8) q(1，9)=1 q(10，8) q(1，1)=2 q(10，8)=2 q(10，7) q(2，8)=2 q(10，7) q(2，2)=2 q(10，6) q(3，7) q(2，2)=2 q(10，5) q(4，6) q(3.例2整数划分问题，空间用于时间，计数排序，对于每个元素，计算列表中小于它的元素的数量。根据数字大小作为下标，存储在表中。字符串匹配，字符串匹配问题：给定一个由n个字符组成的字符串，称

3、为文本t，和一个由m(=n)个字符组成的字符串，称为模式M，问：文本中是否有一个子字符串S，因此S=M？例如：T=abcd，M=bc显然，T的子串是，a，B，C，D，ab，bc，cd，abc，bcd，abcd，其中之一是M，字符串匹配的强力方法，T=N O B O D Y N O T I C E D H I M M=N O T匹配过程：移动比较1。暴力方法，O(n2) 2，Horspool算法，O(n) 3，Boyer-Moore算法，O(n)，Horspool算法，T=t0，t1，tk(=C)，t n-1 M=BARBER，从左向右移动2。如果模式中有当前比较文本的一个元素(设置为C)，但它不是模式的最后一个字符，那么您可以将模式中最右边的C与文本中的C对齐。霍斯普算法，3。如果C只是模式的最后一个字符，但是C没有包含在模式的其他m-1个字符中，那么您可以移动模式的长度并再次开始比较。4.如果C恰好是模式的最后一个字符，但是C包含在模式的其他m-1个字符中，那么您可以将模式中最右边的C与文本中的C对齐。霍斯普算法，如何计算移动距离？图案的长度T(c )=从图案的前m-1个字符中最右边的c到图案的最后一个字符的距离，并且c不包括在图案的前m-1个字符中。在其他情况下，c是文本

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

温馨提示

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

最新文档

评论

0/150

提交评论