算法分析与设计[分治法].ppt_第1页
算法分析与设计[分治法].ppt_第2页
算法分析与设计[分治法].ppt_第3页
算法分析与设计[分治法].ppt_第4页
算法分析与设计[分治法].ppt_第5页
已阅读5页，还剩34页未读， 继续免费阅读

下载本文档

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

文档简介

1、算法分析与设定修订、第二章分治法、第二章分治法、分治法是指二分检索集合了最大与最小要素的分类、2.1分治法的一般方法、问题(n输入)、分治战略DANDC的抽象控制、Procedure DANDC(p，q) global n，A(1:n )； 整数m、p、q； 小规模(p，q )回复(g，q )激励(p )， 如果q)/pmq/rette划分的两个子问题的输入规模大致相等，则划分治理策略DANDC的校正计算时间可以表示为2.2二进制检索，其中，T(n )=-g (n ) n是小的一盏茶，而不是2T(n/2) f(n )，则可以表示为t (n )，并且问题描述可以表示为确定给定元素x是否出现在该表

2、中，则找到该元素在表中的位置为j，否则为j，否则为j。 一般的解决方案(寻找从头至尾)、x、成功和不成功的校正计算时间都是n、河流动力学原理，将问题表示为I=(n，a1，an，x )，如果选择一个下标k，则得到三个子问题： I-1 低1； 搜索中间值*/case xAmid: lowmid 1 /*后半部分return /*搜索成功*/endcase j0 /*检索失败*/End BINSRCH 82，X=101 Lowhighmid 195 697 898 999 OK，x=-14 lowhighmid 195 142 112否，X=82 Lowhighmid 195 697 898 OK，

3、 二分搜索算法的精准性证明满足5个特性的是：如果算法证明算法正确则不进入循环，j=0，如果算法未结束则进入循环与数组a的要素进行比较，如果x=Amid则j=mid，如果检索成功，如果算法未结束则xA(mid )，A(mid 1) 在和A(n )之间缩小的检索如上所述缩小检索区域总是能够以有限步骤出现lowhigh。 在这种情况下，x不在a、j=0、算法结束、在二分搜索算法所需的空间和时间、需要的空间在n个位置保存数组a、以及low的公共需求空间n 5的修正计算时间，相对于修正计算时间，在检索成功的最佳情况和失败的最佳情况检索成功的最坏情况和失败的最坏情况下， 在检索成功的最佳的情况和失败的最佳的情况下，成功检索的检索是n种失败的检索为n 1种，二元比较树，5、7、2、1、3、4、6、8、9、内结点，一次元素体的一方，在1次检索失败的情况下最差情况下的成功检索修正计算时间(logn )最差情况下的不成功检索修正计算时间(logn )最差情况下的成功检索修正计算时间(1)最差情况下

人人文库> 全部分类> 教育资料 > 课设设计

温馨提示

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

最新文档

评论

0/150

提交评论