数据结构与算法(C语言) 教案 第01章 数据结构与算法.docx
《数据结构与算法(C语言) 教案 第01章 数据结构与算法.docx》由会员分享,可在线阅读,更多相关《数据结构与算法(C语言) 教案 第01章 数据结构与算法.docx(13页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、千锋教育数据结构与算法(C语言篇)教学设计课程名称:数据结构与算法(C语言篇)授语年级:授课学期:教师娓名:2020年03月01日(1)解决问题的算法有很多,为了测试某算法效率的高低,需要尽可能 多地编写算法程序与之进行比拟测试,而设计编写算法程序需要大量的时间 和精力。(2)程序运行时间受计算机硬件等环境因素影响,有时会掩盖算法本 身的优劣。例如,八核处理器明显比单核处理器处理程序的速度要快。(3)算法测试数据设计困难,效率高的算法在测试数据规模小时表现 不明显。2 .事前分析法事前分析法指的是设计算法程序之前,根据统计方法对算法进行估算。 一个好的算法所消耗的时间,应该是算法中每条语句执行
2、的时间之和;每条 语句的执行时间是该语句的执行次数与该语句执行一次所需时间的乘积。算法的时间复杂度在134节中的例1-5、例1-6、例1-7中,变量n称为问题规模,算法 中语句的执行次数称为时间频度,记为T(n)。例1-5和例1-7中,当n不断 变化时,时间频度T(n)也会不断变化。如果有某个辅助函数f(n),并且存在一个正常数c使得f(n)XcT(n)恒 成立,那么记作T(nO(f(n)o通常将O(f(n)称为算法的渐进时间复杂度,简 称时间复杂度。使用0()计算时间复杂度的记法称为大0记法。一般情况 下,随着n的增大,T(n)增长最慢的算法为最优算法。利用上述时间复杂度的公式,分别计算例1
3、-5、例1-6、例1-7中算法的 时间复杂度,具体分析如下。(辅助函数f(n)获取执行次数,正常数c视为 单次执行时间,可以忽略。)(1)例1-5的算法时间为2Xn+5,那么f(n)=2n+5。当问题规模n变为 无穷大时,该算法的执行时间可估算为n,使用大。记法表示时间复杂度为 O(n)o(2)例1-6的算法时间为3,贝1J f(n)=3o此值相较于无穷大的n值可忽 略不计,因此使用大0记法表示时间复杂度为0(1)。( 0(1)表示执行次数 或时间是一个常数,不随着n的变化而变化)(3)例 1-7 的算法时间为 3Xn2+3Xn+3,那么 f(n)=3(n 2+n+l)。当问 题规模n变为无穷
4、大时,该算法的执行时间可估算为n 2 ,使用大0记法 表示时间复杂度为0(n2)。通常情况下,将0(1)、0(n)、0(n2)分别称为常数阶、线性阶、平方阶。 除此之外,还有对数阶、指数阶等其他阶。L常数阶例中的算法时间为3,根据上述时间复杂度计算方法可知,该算法的时 间复杂度没有最高阶项,就是一个常数。使用平面直角坐标系表示常数阶, 如下图。问题规模n.线性阶例中的算法时间为2n+5,根据上述时间复杂度计算方法可知,随着问 题规模n变大,时间复杂度成线性增长。使用平面直角坐标系表示线性阶, 如下图。问题规模n2 .平方阶例中的算法执行时间为3(n2+n+l),根据上述时间复杂度计算方法可 知
5、,随着问题规模n变大,时间复杂度线性增长变快。使用平面直角坐标系 表示平方阶,如下图。问题规模n算法的空间复杂度了解算法的空间复杂度之前,需要先理解算法存储量的概念。算法的存 储量指的是算法执行过程中所需的最大存储空间,其主要包括3个局部:输 入/输出数据所占空间、程序代码所占空间、程序运行临时占用空间。L输入输出数据所占空间算法的输入/输出数据所占用的存储空间是由要解决的问题决定的,是 通过参数表由调用函数传递而来的,它不会随着算法的不同而改变,因此在 算法比拟时不予考虑。2 .程序代码所占空间算法的程序代码所占用的存储空间与程序的长度成正比,要压缩这局部 存储空间,就必须编写出较短的程序。
6、程序代码本身所占空间对不同算法来 说不会有数量级的差异。3 .程序运行临时占用空间根据程序在运行过程中临时占用存储空间的不同,可以将算法分为两 类。(1)原地算法:只占用较小的临时空间,且占有量不会随着问题规模n 的改变而改变。(2)非原地算法:占用临时空间的大小与问题规模n有关,n越大占用 的临时空间越大。通过计算算法存储量可以得到算法的空间复杂度,算法空间复杂度的计 算公式记作S(nO(f(n),其中,n为问题的规模,f(n)为关于n所占存储空 间的函数。随着问题规模n的增大,算法存储量的增长率与f(n)的增长率相 同。习题教材第1章习题课程名称第1章数据结构与算法计划 学时2学时内容分析
7、本章主要介绍数据结构的概念、逻辑结构与物理结构、算法的概念教学目标 与教学要求要求学生了解数据结构的概念与专业术语、了解数据的逻辑结构与物理 结构、了解算法的概念与特性教学重点逻辑结构与物理结构、算法的概念教学难点逻辑结构与物理结构、算法的概念教学方式课堂讲解及ppt演示教学过程第一课时(数据结构的概念、逻辑结构与物理结构)0了解数据结构与算法i.讲述数据结构与算法内容,引出本课时主题。数据结构是计算机专业的一门基础课,其主要研究程序设计中的操作对 象及它们之间的关系。算法指的是解决问题的策略,只要有符合一定规范的 输入,在有限时间内就能获得所要求的输出。虽然数据结构与算法属于不同 的研究课题
8、,但优秀的程序设计离不开二者的相辅相成。因此,本章将主要 介绍数据结构与算法的基本概念,包括数据结构的基本术语、数据的结构分 类以及算法的各种特性。2.明确学习目标(1)能够了解数据(2)能够了解数据元素与数据项(3)能够了解数据对象(4)能够掌握数据结构(5)能够掌握逻辑结构(6)能够掌握物理结构0知识讲解数据数据(Data)在计算机科学中是指计算机操作的对象,是输入到计算机 中被计算机程序处理的符号集合。例如,一个读取终端输入的程序,其操作 的对象可能是字符串,那么字符串就是计算机程序处理的数据。数据不仅可 以是整型、字符型等数值类型,也可以是音频、图片、视频等非数值类型。综上所述,数据的
9、本质就是符号,且这些符号都满足以下特定的需求。(1)可以输入到计算机中。(2)可以被计算机程序处理。其中数值类型的数据可以被执行数值计算,而非数值类型的数据可以被 执行非数值的处理,例如,音频、图片、视频等资源在计算中都是被编码转换为字符数据来处理的。 数据元素与数据项数据元素(Data Element)是组成数据的基本单位。数据的基本单位是 一种抽象的概念,并没有具体的数值化标准。例如,可以将公司看作一个数 据元素,也可以将员工视为一个数据元素。数据元素由数据项组成,并且数据项是数据不可分割的最小单位。例如, 将公司看作一个数据元素,那么行政部、人事部、财务部都可以视为该元素的 数据项,也可
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构与算法C语言 教案 第01章 数据结构与算法 数据结构 算法 语言 01
限制150内