- 1、本文档共95页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 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 最坏情况和平均情况分析;最坏情况分析;平均情况分析;;最优算法
您可能关注的文档
- 第四章 节 种群及其基本特征2013(普通生态学).ppt
- 第四章 节 营销调研.ppt
- 第四章 节 董事会制度(公司治理学课件).ppt
- 第四章 节 财务预测 1.ppt
- 第四章 节 超敏反应.ppt
- 第四章 节 酸碱平衡 PPT课件.ppt
- 第四章 节 酸碱平衡18713 .ppt
- 第四章 节 非瓦尔拉斯均衡学派(西方经济学流派(石家庄经济学院(王志伟教材)) .ppt
- 第四章 节 (mba) .ppt
- 第四章 节 -护士言谈礼仪 .ppt
- 2025年金肯职业技术学院单招职业适应性测试题库带答案.docx
- 2025年钦州幼儿师范高等专科学校单招综合素质考试题库完美版.docx
- 2025年钟山职业技术学院单招职业适应性考试题库参考答案.docx
- 2025年金华职业技术学院单招职业技能测试题库附答案.docx
- 2025年闽南理工学院单招职业技能测试题库审定版.docx
- 2025年闽南理工学院单招综合素质考试题库审定版.docx
- 2025年闽南理工学院单招职业倾向性考试题库汇编.docx
- 2025年闽南理工学院单招职业倾向性考试题库推荐.docx
- 2025年闽北职业技术学院单招综合素质考试题库1套.docx
- 2025年长沙轨道交通职业学院单招职业技能考试题库一套.docx
最近下载
- 2017年山东省青岛市城阳七年级英语下册 Unit 1-2 复习练习题(无答案)(新版)人教新目标版.doc VIP
- 输变电工程标准工艺(变电工程土建分册)2022版.pdf VIP
- 个人防护用品培训.ppt VIP
- 启动仪式开业典礼模板《启动仪式全程安排及总结》PPT课件.pptx VIP
- 如何做一个出色的班组长.pptx VIP
- 2025年度卫生招聘考试(财务)新版真题卷(附详细解析).docx VIP
- 2025必威体育精装版乡村医生考试试题库含答案.docx VIP
- 全国突发急性传染病防控技能竞赛笔试复习测试附答案(一).doc
- 如何做一个出色的班组长.pptx VIP
- 560期货交易技术策略系统.docx VIP
文档评论(0)