算法设计与分析 ( 第1章 节 算法分析基本概念 ).pptVIP

算法设计与分析 ( 第1章 节 算法分析基本概念 ).ppt

  1. 1、本文档共95页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
  5. 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
  6. 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们
  7. 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
  8. 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
算法设计与分析 ( 第1章 节 算法分析基本概念 ).ppt

算法设计与分析;课程简介(课程设置意义);课程简介(课程目的);教材与参考书;课时安排 授课 :32学时 考试方式 课堂参与(10分)、编程实践(40分)、考试成绩(50分) ;伪代码的使用(3);;1.1 引言; 1.1 引言——历史背景 ; 1.1 引言——历史背景 ; 1.1 引言——算法一词的来历 ; 1.1 引言——算法一词的来历 ; 1.1 引言——算法一词的来历 ; 1.1 引言——算法的定义和特征 ; 1.1 引言——算法的定义和特征 ;1.2 算法复杂性分析; 1.2.1 算法复杂性分析的必要性; 定义: 查找算法的平均查找长度 (Average Search Length) 为确定记录在查找表中的位置,需和给定值 进行比较的关键字个数的期望值 其中: n 为表长,Pi 为查找表中第i个记录的概率, 且   , Ci为找到该记录时,曾和给定 值比较过的关键字的个数。; 在等概率查找的情况下, 顺序表查找的平均查找长度为: ;ST.elem;1.2.1 算法复杂性分析的必要性; 先看一个具体的情况,假设:n=11;假设 n=2h-1 并且查找概率相等 则 在n50时,可得近似结果 ;1.2.1 算法复杂性分析的必要性;插入排序;;;;; 输入:n个元素的数组A[1..n] 输出:按非降序排列的数组A[1..n] 1. for i←2 to n 2. x ←A[i] 3. j ←i-1 4. while (j〉0)and(A[j]〉x) 5. A[j+1] ←A[j] 6. j ←j-1 7. end while 8. A[j+1] ←x 9. end for;算法分析;分别为; 选择排序的基本思想是:每一趟 (例如第 i 趟,i = 1, …, n-1) 在后面的 n-i+1 个待排序对象中选出元素最小的对象, 作为有序对象序列的第 i 个对象。待到第 n-1 趟作完,待排序对象只剩下1个,就不用再选了。;;;选择排序算法(p8);算法分析 ;归并排序;08 21 25 25* 49 62 72 93 ;合并两个已排序的表(MERGE)(P6);合并算法分析;自底向上合并排序算法;;自底向上合并排序算法(P10);自底向上合并算法分析;令k=log n,则元素比较次数最少为;各种排序方法的比较; 小结;小结; 1.2.2 算法的输入规模和运行时间的阶;同一个问题往往可以由不同的算法解决,但是算法不同,效率也不同。对于处理数量较少的数据项而言,算法之间效率的差异也许微不足道,但是当数据量增长时,这种差异就会成比例地增长。为了使得算法效率具有可比性,Juris Hartmanis和Richard E.Stearns引入一种称为“计算复杂度”的度量标准来衡量一种算法的难易程度。 计算复杂度表示应用一种算法需要付出多大的努力或是成本是多少。 ; 1.2.2 算法的输入规模和运行时间的阶; 1.2.2 算法的输入规模和运行时间的阶;;;;;; 1.2.2 算法的输入规模和运行时间的阶;;;;;;;复杂性类与o符号;;;1.3如何估计算法的运行时间;;1.3.1 计算迭代次数;;;;1.3.2 计算基本运算的频度 ;;;1.3.2 使用递归方程;1.3.4 最坏情况和平均情况分析;最坏情况分析;平均情况分析;;最优算法

文档评论(0)

yuzongxu123 + 关注
实名认证
文档贡献者

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

1亿VIP精品文档

相关文档