四川工业科技学院标准教案纸
课堂教学题目 第14讲算法复杂度估算与程序编码 授课时间 教学目标 地点 通过本讲的学习，熟悉编程规范，掌握算法复杂度估算的方法 教学重点 教学难点 程序算法设计工具 程序算法设计工具 教学内容方法与手段： 教学方法：讲授法、演示法、案例分析法 教学手段：多媒体教学 教学过程 导入新课 简单回顾上次课的内容，引入新课 新课教学 一、算法复杂度评估 算法复杂度是对程序算法是否复杂的量化说明。通常，可以从时间和空间两个方面，对程序算法进行复杂度评价。 时间复杂度：由算法执行所耗费时间决定。通常，算法中语句的执行次数越多，其花费时间就越多，则时间复杂度就越高。 空间复杂度：由算法所需存储空间决定。通常，程序中定义的数据元素越少，采用的数据类型越简单，则空间复杂度就越低。 定量度量程序复杂程度的方法很有价值： 把程序的复杂程度乘以适当常数即可估算出软件中错误的数量以及软件开发需要用的工作量， 定量度量的结果可以用来比较两个不同的设计或两个不同算法的优劣； 程序的定量的复杂程度可以作为模块规模的精确限度。 1、McCabe方法
3
McCabe方法根据程序控制流的复杂程度定量度量程序的复杂程度，这样度量出的结果称为程序的环形复杂度。 流图实质上是“退化了的”程序流程图，描绘程序的控制流程，不表现对数据的具体操作以及分支或循环的具体条件。 这是一种基于控制流的广泛应用的程序算法复杂度评估方法。其定义程序算法复杂度为强连通程序图中线性无关的有向环的个数。计算公式是： V（G）= m – n + 1 ，其中，V是强连通程序图中的环数，m是弧数，n是节点数。 二、程序编码 编程语言可分为机器语言、汇编语言、传统高级语言、结构化语言、面向对象语言、第四代程序语言。有必要根据问题性质选择合适的程序语言，以提高编程质量。 编程规范即是为提高程序可读性、可理解性而需要遵守的约定。一些常用的编码规范有：程序注释、标识符命名、程序编排格式。 程序算法设计还必须考虑程序的运行效率，其由程序的算法复杂度、程序中数据的类型、程序编译的优化程度等诸多因素决定。 1、选择程序设计语言 程序设计语言是人和计算机通信的最基本的工具，会影响人的思维和解题方式，影响人和计算机通信的方式和质量，影响其他人阅读和理解程序的难易程度。 选择适宜的程序设计语言的原因： 根据设计去完成编码时，困难最少； 可以减少需要的程序测试量； 可以得到更容易阅读和更容易维护的程序。 2、编程规范 源程序代码的逻辑简明清晰、易读易懂是好程序的一个重要标准，为了做到这一点，应该遵循下述规则。 (1)程序内部的文档 所谓程序内部的文档包括恰当的标识符、适当的注解和程序的视觉组织等。 标识符：含义鲜明的名字、缩写规则一致、为名字加注解； 3
注解：正确性，简要描述模块的功能、主要算法、接口特点、重要数据以及开发简史或解释包含这段代码的必要性； 视觉组织：适当的阶梯形式使程序的层次结构清晰明显。 (2) 数据说明 数据说明的原则： 数据说明的次序应该标准化； 当多个变量名在一个语句中说明时，应该按字母顺序排列这些变量； 如果设计时使用了一个复杂的数据结构，则应该用注解说明用程序设计语言实现这个数据结构的方法和特点。 (3) 语句构造 下述语句构造的原则有助于使语句简单明了： 不要为了节省空间而把多个语句写在同一行； 尽量避免复杂的条件测试； 尽量减少对“非”条件的测试； 避免大量使用循环嵌套和条件嵌套； 利用括号使逻辑表达式或算术表达式的运算次序清晰直观。 (4)输入输出 在设计和编写程序时需考虑有关输入输出风格的规则： 对所有输入数据都进行检验； 检查输入项重要组合的合法性； 保持输入格式简单； 使用数据结束标记，不要要求用户指定数据的数目； 明确提示交互式输入的请求，详细说明可用的选择或边界数值； 程序设计语言对格式有严格要求时，应保持输入格式一致； 设计良好的输出报表； 给所有输出数据加标志。 (5)效率 效率主要指处理机时间和存储器容量两个方面。 效率是性能要求，因此应该在需求分析阶段确定效率方面的要求； 3
效率是靠好设计来提高的； 程序的效率和程序的简单程度是一致的，不要牺牲程序的清晰性和可读性来不必要地提高效率。 课堂小结 作 业 软件工程线上平台习题 教学反思或在讲述相关知识点时多举实例进行分析，以便于学生理解 反馈记录
3
因篇幅问题不能全部显示，请点此查看更多更全内容