算法分析第3章.ppt

  1. 1、本文档共22页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
第3章 蛮力法 蛮力法一种简单直接地解决问题的方法,常常直接基于问题的描述和所涉及的概念定义。 虽然巧妙和高效的算法很少来自于蛮力法,但我们不应该忽略它作为一种重要的算法设计策略的地位。第一,和其他某些策略不同,我们可以应用蛮力法来解决广阔领域的各种问题。第二,对于一些重要的问题来说(比如:排序、查找、矩阵乘法和字符串匹配),蛮力法可以产生一些合理的算法,它们多少具备上些实用价值,而且并不限制实例的规模。第三,如果要解决的问题实例不多,而且蛮力法可以用一种能够接受速度对实例求解,那么,设计一个更高效算法所花费的代价很可能是不值得的。第四,即使效率通常很低,仍然可以用蛮力法解决一些小规模的问题实例。最后,一个蛮力算法可以为研究或教学目的的服务。 3.1 选择排序和冒泡排序 算法 SelectionSort(A[0..n-1]) //该算法用选择排序对给定的数组排序 //输入:一个可排序数组A[0..n-1] //输出:非降序排序的数组A[0..n-1] for i←0 to n-2 do min ←I for j ←i+1 to n-1 do if A[j][min] min ←j swap A[i] and A[min] | 89 45 68 90 29 34 17 17 | 45 68 90 29 34 89 17 29 | 68 90 45 34 89 17 29 34 | 90 45 68 89 17 29 34 45 | 90 68 89 17 29 34 45 68 | 90 89 17 29 34 45 68 89 | 90 3.1.2 冒泡排序 89 45 68 90 29 34 17 45 89 68 90 29 34 17 45 68 89 90 29 34 17 45 68 89 29 90 34 17 45 68 89 29 34 90 17 45 68 89 29 34 17 90 45 68 89 29 34 17 90 45 68 29 89 34 17 90 45 68 29 34 89 17 90 45 68 29 34 17 89 90 对于所有规模为n的数组来说,该冒泡排序版本的键值比较次数都是相同的,我们可以用下面这个求和表达式来表示。它和选择排序的表达式几乎是完全相同的: 3.2 顺序查找和蛮力字符串匹配 3.2.1 顺序查找 该算法只是简单地将给定列表中的连续元素和给定的查找键作比较,直到遇到一个匹配的元素(查找成功),或者在遇到元素前就遍历了整个列表(失败查找) 算法 SequentialSearch2(A[0..n],K) //顺序查找的算法实现,它用了查找键来做限位器 //输入:一个n个元素的数组A和一个查找键K //输出:第一个值等于K的元素的位置,如果找不到这样的元素,返回-1 A[n]←K i←0 while A[i] ≠ K do i ←i+1 if in return i else return -1 如果已知给定数组是序的,我们可以对该算

文档评论(0)

精品文库 + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档