大学选修数据结构绪论.ppt

影响算法执行的因素： ①算法实现后所消耗的时间** ②算法实现后所占存储空间的大小* ③算法是否易读、易移植等等其它问题 影响时间特性的四个因素： ①程序运行时输入数据的总量 ②对源程序编译所需的时间 ③计算机执行每条指令所需的时间 ④程序中指令重复执行的次数* [定义] 语句频度：语句重复执行的次数 程序运行时间 渐近时间复杂度（时间复杂度）T（n） 算法中基本操作重复执行的次数是问题规模n的某个函数 f（n），算法的时间度量记作： T（n）= O（ f（n）） 它表示随问题规模n的增大，算法执行时间的增长率和 f（n）的增长率相同。 渐近空间复杂度（空间复杂度）S（n） S（n）= O（ g（n）） 运算法则： 设：T1(n)=O( f(n) )，T2(n)=O( g(n) ) 加法规则：T1(n)+T2(n) = O( max{ f(n), g(n) } ) 乘法规则：T1(n) ·T2(n) = O( f(n) · g(n) ) 程序运行时间比较 T（n）=O（f（n）） T(n) n 0 1000 2000 3000 5 10 15 20 25 2n n3 100n 5n2 logn 2100 △n △ T(n) 设： T(x) ： 取变量或常量x之值所消耗时间 T(.V)： 取变量V之地址所消耗的时间 T(=) ： 赋值所消耗时间 T(θ) ： 执行基本运算θ所耗时间 T(call/return)：执行函数调用和返回所耗时间 T(par) ： 将参数par传给函数所消耗时间 ～ (1) 表达式和赋值语句 exp::=常数 | 变量 | F-name(e1,e2,…,em) | (exp θ exp) T(v=exp)=T(.v)+T(=)+T(exp) T(exp θ exp)=T(exp)+T(θ)+T(exp) T(F-name(e1,e2,…,em))=T(call/return)+mT(par)+T(F-body) 例： T(c=a+b)=T(.c)+T(=)+T(a)+T(+)+T(b) 相应的汇编程序为： load a in R1 load b in R2 add R2 to R1 load .c in R2 store R1 in R2 ～ ～ 通常取O(1) 第1章 绪 论 Slide. 1 - * D.S. A. 2010 ’秋 数据结构 哈尔滨工业大学软件与网络技术学院 D.S. Page. * 第一章 绪 论 数据结构与算法 Data structures and Algorithm 讲课学时：52，实验学时：12，课程设计：2周 教学安排： 期末考试占70%，实验成绩占20% ，平时作业占10% 考核要求： 计算机导论 数字逻辑 计算机组成技术 操作系统 数据库系统 课程设计 计算机网络 编译原理 数据结构与算法 数据结构与算法 课程设计 多核程序设计 数据库系统 Linux操作系统* 程序设计语言 用户界面设计 面向对象技术 与UML Java语言 程序设计实践 面向服务的 计算技术 .Net C++语言 J2EE 软件开发实践 软件外包开发技术* 英语限选 军训 大学外语 体育 政治 大学外语 体育 马哲 英语限选 体育 英语限选 体育 英语口语 英语限选 英语口语 工科数析Ⅰ 代数与几何 概率论与数理统计 离散数学 运筹学 算法设计与分析 工科数析Ⅱ 理论系列 系统系列 工具系列 工程系列 管理系列 其他课程 第一 学期 第二 学期 第三 学期 第四 学期 第五 学期 第六 学期 第七学期 第八学期 系统分析与设计 软件工程概论 软件项目管理 软件开发过程管理 软件