计算学科中的核心概念_第1页
计算学科中的核心概念_第2页
计算学科中的核心概念_第3页
计算学科中的核心概念_第4页
计算学科中的核心概念_第5页
已阅读5页,还剩3页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、第第4章章 计算机学科中的核心概念计算机学科中的核心概念 算法描述(算法描述(p79) 例例1、欧几里得算法、欧几里得算法求两个正整数的求两个正整数的m和和n的最大的最大 公因子。公因子。 一、算法(一、算法(algorithm) 定义(非形式化):一个算法,就是一个有穷规则的集合,其定义(非形式化):一个算法,就是一个有穷规则的集合,其中中 之规则规定了一个解决某一类特定类型问题的运算序列。之规则规定了一个解决某一类特定类型问题的运算序列。 特征特征 有穷性有穷性 确定性确定性 初始值(输入)初始值(输入) 结果(输出)结果(输出) 能行性能行性 形式化定义(形式化定义(q,i, ,f) 2

2、、算法的定义与特征、算法的定义与特征 3、算法实例(表示方法:自然语言、算法实例(表示方法:自然语言流程图流程图 程序设计语言)程序设计语言) 例例1,求,求 例例2,求解调合级数,求解调合级数 hn= 例例3,求解斐波那契数:,求解斐波那契数:0,1,1,2,3,5,8, 13,21,34, 每个数都是前两数之和每个数都是前两数之和 f0=1,f1=1,fn+2=fn+1+fn,n0 100 k=1k111213141n+ + + + +4、算法分析、算法分析 内容内容 (1) 时间复杂度时间复杂度 (2) 空间复杂度空间复杂度 (3) 便于阅读、修改与测试便于阅读、修改与测试 常见的复杂度

3、等级常见的复杂度等级 (1) o(l):常数级常数级 (2) o(logn):对数级对数级 (3) o(n):线性级线性级 (4) o(nc):多项式级多项式级 (5) o(cn):指数级指数级 (6) o(n!):阶乘级阶乘级二、数据结构二、数据结构1、数据结构的基本概念、数据结构的基本概念 定性的数学模型:非数值性的数据结构及其定性的数学模型:非数值性的数据结构及其 运算运算 数据逻辑结构:数据逻辑结构:ds= 数据的存储结构:顺序,链式数据的存储结构:顺序,链式 数据结构的基本运算:建立、清除、插入元数据结构的基本运算:建立、清除、插入元 素、删除元素、更新元素、查找元素、排序素、删除元

4、素、更新元素、查找元素、排序 2、线性表与数组、线性表与数组 线性表线性表 数组数组3、树与二叉树、树与二叉树 树树 二叉树二叉树4、图、图三、程序三、程序程序程序 = 算法算法 + 数据结构数据结构四、软件四、软件1、系统软件、系统软件2、支撑软件、支撑软件3、应用软件、应用软件五、硬件五、硬件六、十二个反复出现的核心概念六、十二个反复出现的核心概念1、绑定(、绑定(binding)2、大问题的复杂性(、大问题的复杂性(complexity of large problems)3、概念和形式模型(、概念和形式模型(conceptual and format models)4、一致性和完备性(、一致性和完备性(consistency and completeness)5、效率(、效率(efficiecy)6、演化(、演化(evolution)7、抽象层次(、抽象层次(levels of abstraction)8、按空间排序(、按空间排序(ordering in space)9、按时间排序(、按时间排序( ordering in time)10、重用(、重

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论