版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
算法与数据结构主讲人:黄紫成考核方式平时30%+期末70%平时如何考核??作业得分:书面作业+上机实验表现得分:出勤、上机选用教材算法与数据结构,宁正元清华大学出版社主要参考文献严蔚敏吴伟民数据结构(C语言版)清华大学出版社耿国华:数据结构——C语言描述高等教育出版社2005廖明宏:数据结构与算法(第4版)高等教育出版社2007算法导论机械工业出版社绪论学习算法与数据结构的意义及要求算法与数据结构的主要内容根本术语算法描述及分析1.1学习数据结构的意义及要求意义1、算法和数据结构是计算机科学的两大支柱研究算法的科学计算机科学早期定义为近期定义为研究数据的科学2、数据结构是程序设计的根底程序=算法+数据结构数据结构是设计OS、DBMS、编译等系统程序和各种应用程序的重要基础3、数据结构是计算机专业的一门综合性专业根底课是计算机专业本科生必修课程是计算机研究生入学考试科目是软件人员水平考试内容要求掌握各类根本数据结构类型和相应的存储结构提高阅读和编写算法的能力能针对给定问题,选择相适应的数据结构,并能设计和分析算法1.2数据结构的主要内容350014:059187650125:固定20080101:学号结论1:杂乱的数据不能表达和交流信息e.g.2号码簿〔a1,b1〕〔a2,b2〕〔a3,b3〕…〔an,bn〕其中:ai为某人姓名,bi为此人的号码要求:设计一个算法,给定某人的姓名时,能查出此人的号码如果姓名和电话号码的排列无规律,则只能逐一比较姓名进行查找如果姓名按字典顺序组织,则查找会快捷很多结论2:数据之间是有联系的这些联系常常影响算法的选择和效率,DS就是要研究数据之间的联系e.g.3井字棋对弈树结论3:数据之间是有结构的例3中数据之间呈分层结构〔树状结构〕DS就是要研究数据之间的各类结构e.g.4企业员工信息管理系统设每个员工包含:员工姓名、性别、出生年月、员工编号、工资等对员工信息常有如下操作:查找:某人是否是该企业的员工?插入:新进员工的信息录入删除:离职员工或因其他原因不在该公司继续任职结论4:在某种数据结构上可定义一组运算DS就是要研究各类数据结构上的各种运算综上所述:数据结构主要研究内容数据的各种逻辑结构和物理结构,以及它们之间的相应关系并对各种结构定义相适应的各种运算设计出相应的算法分析算法的效率常见的数据结构有:数组、栈、队列、表、串、树、图和文件等1.3算法描述和算法分析一、算法概述1、什么是算法?2、算法解决的问题?3、算法的特性4、算法的表示二、算法的设计原那么三、算法效率的衡量方法和准那么1、事后统计法2、事前分析估算法(环路复杂度,时空复杂度)一、算法概述
1、什么是算法?e.g.求解两个整数的最大公因子的解题步骤要求解的问题描述为:“给定两个正整数m和n,求它们的最大公因〞。欧几里德当时给出的算法如下:⑴以n除m,并令所得余数为r〔必有r<n〕;⑵假设r=0,输出结果n,算法结束;否那么继续步骤⑶;⑶令m=n和n=r,返回步骤⑴继续进行。算法就是求解问题的方法和步骤算法是为了解决某类问题而规定的一个有限长的操作序列。《计算机程序的艺术》〔ArtofComputerProgram〕中非形式化的定义是:一个算法,就是一个有穷规那么的集合,其中之规那么定义了一个解决某一特定类型问题的运算序列。例如:排序问题〔非降序排列〕输入:n个数组成的序列<a1,a2,a3,…an>输出:对输入序列的一个重排<a’1,a’2,a’3,…a’n>其中:a’1≤a’2≤a’3≤…≤a’n2、算法解决的问题因特网〔数据传输路径,搜索引擎SearchEngineSpider〕电子商务〔平安方面——密钥〔数值算法、数论知识〕〕算法解决的具体的问题道路交通〔确定两个交叉路口间的最短路径〕矩阵乘法顺序〔A1A2A3A4A5A6A7〕旅行商问题〔TravelingSalesmanProblem〕说明算法:可供选择的方案多实际应用性强3、一个算法必须满足以下五个重要特性
1.有穷性
2.确定性3.可行性4.有输入5.有输出1.有穷性对于任意一组合法输入值,在执行有穷步骤之后一定能结束,即:算法中的每个步骤都能在有限时间内完成。
2.确定性
对于每种情况下所应执行的操作,在算法中都有确切的规定,使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下,算法都只有一条执行路径。3.可行性算法中的所有操作都必须足够根本,都可以通过已经实现的根本操作运算有限次实现之。4.有输入作为算法加工对象的量值,通常表达为算法中的一组变量。有些输入量需要在算法执行过程中输入,而有的算法外表上可以没有输入,实际上已被嵌入算法之中。5.有输出它是一组与“输入〞有确定关系的量值,是算法进行信息加工后得到的结果,这种确定关系即为算法的功能。4、算法的表示自然语言表示流程图表示
N—S图表示
伪代码表示程序语言表示流程图表示欧几里德算法的流程图表示noyesmmodn→rend读入m,nr=0beginN→m,r→n输出nm,n为正整数,算法求其最大公因子N-S图表示读入正整数m,n
读入正整数m,nmmodn→rm→r当r≠0反复做n→m,r→n
n→m,r→nmmodn→r
mmodn→r直到r=0时止输出最大公因子n输出最大公因子n(a)当型循环结构实现(b)直到型循环结构实现欧几里德算法的N-S图表示伪代码表示Begin(算法开始)Read(m,n)mmodn→rwhiler≠0do{n→mr→nmmodn→r}write(n)End(算法结束)程序语言表示#include<stdio.h>main(){intm,n,r;printf(“请输入两个正整数:〞);scanf(“%d%d〞,&m,&n);printf(“\n%d和%d的最大公约数是:〞,m,n);r=m%n;while(r!=0){m=n;n=r;r=m%n;}printf(“%d\n〞,n);}算法与程序的区别算法是解决问题的一种方法或一个过程,考虑如何将输入转换成输出,一个问题可以有多种算法程序是用某种程序设计语言对算法的具体实现程序可以是错误的,算法必须是正确的有穷性描述方法正确性主要区别程序可以是无穷的,例如OS,算法是有穷的程序是用程序设计语言描述,在机器上可以执行,算法还可以用框图、自然语言等方式描述二、算法设计的原那么设计算法时,通常应考虑到达以下目标:1.正确性2.可读性3.健壮性4.高效率与低存储量需求1.正确性
无歧义,满足问题规格说明2.可读性
1.程序结构清晰,层次清楚2.变量名命名标准易懂3.提供程序注释3.健壮性对非法数据的处理4.高效率与低存储量需求
通常,效率指的是算法执行时间;存储量指的是算法执行过程中所需的最大存储空间,两者都与问题的规模有关。三、算法效率的衡量方法和准那么通常有两种衡量算法效率的方法:
事后统计法事前分析估算法(定量与定性)缺点:1.必须执行程序2.其它因素掩盖算法本质算法的环路复杂度(定量)欧几里德算法流程图的程序图(强连通图)欧几里德算法的流程图表示noyesmmodn→rend读入m,nr=0beginN→m,r→n输出nV(G)=e-n+p其中:V(G)是图G中环路的个数;e是图G中有向弧的条数,包括由出口到入口增加的一条虚弧;n是图G中结点的个数;p是图G中连通分量的个数,对于连通图而言p恒为1。在设计算法时,一般地应控制模块的环路复杂度在10以内为宜。在设计算法时,一般地应控制模块的环路复杂度在10以内为宜。时间复杂度大O方法执行一个算法的时间代价,算法中每条语句在计算机上执行的时间总和每条语句的执行时间=执行该语句一次所需的时间X该语句执行的次数〔也称之为频度〕语句执行时间与机器性能有关,可假设执行每条语句所需的时间均为单位时间。因此,对算法执行时间的讨论就可以转化为对算法中所有语句的执行次数〔即频度〕的讨论。例1(计算每条语句的频度)两个n*n矩阵相乘的算法描述如下:
⑴for(i=1;i<=n;i++)/*n+1次*/⑵for(j=1;j<=n;j++)/*n(n+1)次*/⑶{c[i][j]=0;/*n2次*/⑷for(k=1;k<=n;k++)/*n2(n+1)次*/⑸c[i][j]=c[i][j]+a[i][k]*b[k][j];/*n3次*/⑹}该算法的时间消耗T(n)可表示为T(n)=2n3+3n2+2n+1T(n)与n3是同阶函数或者说是同量级的。引入大O记号可记作T(n)=O(n3)假设,随着问题规模n的增长,算法执行时间的增长率和f(n)的增长率相同,那么可记作:T(n)=O(f(n))称T(n)为算法的(渐近)时间复杂度。例2(计算最大频度)x=0;for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x++;
T(n)=??算法时间复杂度的估算基于算法中根本操作的重复执行次数,或处于最深层循环内的语句的频度。两个矩阵相乘voidmult(inta[],intb[],int&c[]){
//以二维数组存储矩阵元素,c为a和b的乘积for(i=1;i<=n;++i)
for(j=1;j<=n;++j){c[i,j]=0;
for(k=1;k<=n;++k)c[i,j]+=a[i,k]*b[k,j];
}//for}//mult根本操作:乘法操作时间复杂度:
O(n3)起泡排序voidbubble_sort(int&a[],intn){
//将a中整数序列重新排列成自小至大有序的整数序列。for
(i=n-1,change=TRUE;i>1&&change;--i)}//bubble_sort根本操作:赋值操作时间复杂度:
O(n2){
change=FALSE;
//change为元素进行交换标志
for(j=0;j<i;++j)
if(a[j]>a[j+1])
{
a[j]←→a[j+1];
change=TRUE;}}//一趟起泡计算机硬件不断开展,还有必要研究算法吗?插入排序时间:C1n2,计算机A合并排序时间:C2nlog2n计算机B对100万个数的数组排序A:2n2,每秒执行10亿条指令B:50nlog2n,每秒执行100万条指令A、B排序这些数花费时间??2×(106)2条指令109条指令/秒=2000秒50×106log2106107条指令/秒≈100秒
算法的存储空间需求算法的空间复杂度定义为:
表示随着问题规模n的增大,算法运行所需存储量的增长率与g(n)的增长率相同。S(n)=O(g(n))算法的存储量包括:1.输入数据所占空间2.程序本身所占空间3.辅助变量所占空间假设输入数据所占空间只取决于问题本身,和算法无关,那么只需要分析除输入和程序之外的辅助变量所占额外空间。假设所需额外空间相对于输入数据量来说是常数,那么称此算法为原地工作。
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 小学四年级主题班会《我的目标》教学设计
- 初中地理七年级上册《气温分布规律与等温线判读》教学设计
- 六年级道德与法治下册《权利受保护》教学设计
- 高中历史选择性必修2第五单元交通与社会变迁整合教学设计
- 小学四年级道德与法治 教学设计 我是小小志愿者:从校园走向社区的成长之路
- 高一英语教学设计:初高中衔接期音标重构与基础句法夯实
- 小学四年级道德与法治为父母分担教学设计
- 高二地理湘教版选择性必修1岩石圈物质循环教学设计
- 八年级物理《简单机械》复习课深度教学设计
- 小学三年级美术教学设计《素布彩绣》非遗技艺与审美育人实践研究
- 电商平台商家入驻合作协议三篇
- VDA6.3 过程审核-2-全套内容含审核计划、审核纪录-2026
- 金川集团社招考试试题及答案
- 创伤后骨髓炎防控与诊疗专家共识
- 山西矿山答辩题库
- 2026年第43届全国中学生物理竞赛复赛理论试题及详细解答
- 2026年长期照护师资格考试试卷及答案(共十四套)
- 2026年事业单位(D类)《职业能力倾向测验》考试真题及答案
- 2026-2030中国氧化钇纳米颗粒行业应用动态及未来需求预测研究报告
- 抽纸厂人员岗位责任制度
- 2026年高校纪检审计岗位高频面试题包含详细解答
评论
0/150
提交评论