《可视化计算》第2章算法设计与可视化(A)

1、可视化计算第2章 算法设计与可视化(A) 第2章 算法设计与可视化 PART A 可视化计算 可视化计算第2章 算法设计与可视化(A)2 学习目标 程序与算法有哪些异同? 算法有哪些基本特性？ 算法的效率如何度量？ RAPTOR如何实现计算可视化？ 如何为算法设计做准备？ 可视化计算第2章 算法设计与可视化(A)3 算法定义 算法是在有限步骤内求解某一问题所使用算法是在有限步骤内求解某一问题所使用 的一组定义明确的规则。的一组定义明确的规则。 通俗来说，就是通过计算来解决问题的过程，通俗来说，就是通过计算来解决问题的过程， 在这个过程中，无论是形成解题思路还是编写在这个过程中，无论是形成解题思

2、路还是编写 程序，都是在实施某种算法程序，都是在实施某种算法 不同的是：前者是推理实现的算法，后者是操不同的是：前者是推理实现的算法，后者是操 作实现的算法作实现的算法 所以，程序是使用计算机实现的算法；而算法所以，程序是使用计算机实现的算法；而算法 则不一定需要有计算机才能实现则不一定需要有计算机才能实现 可视化计算第2章 算法设计与可视化(A)4 算法的特性 算法具有五个基本特性： 输入（具有零个或多个输入） 输出（一或多个输出） 有穷性（自动结束而不会出现无限循环） 确定性（每一步骤的含义，不会出现二义性） 可行性（能够通过执行有限次数完成） 可视化计算第2章 算法设计与可视化(A)5

3、算法设计的要求 正确性正确性 可读性可读性 健壮性健壮性 时间效率高时间效率高 存储量需求低存储量需求低 可视化计算第2章 算法设计与可视化(A)6 正确性正确性的层次的层次 算法程序没有语法错误; 算法程序对于合法的输入数据能够产生满 足要求的输出结果; 算法程序对于非法的输入数据能够得出满 足规格说明的结果; 算法程序对于精心选择的，甚至刁难的测 试数据都有满足要求的输出结果。 可视化计算第2章 算法设计与可视化(A)7 可读性可读性 为了便于阅读、理解和交流，可读性要素： 增加算法文件名、子图、子程序、算法样本数 据文件名的可读性； 在算法语句中增加注释语句，说明重要变量、 决策语句的用

4、途； 将算法有关的文档整理在一个目录中 可视化计算第2章 算法设计与可视化(A)8 健壮性健壮性 能对输入数据不合法的情况做合适的处理 比如输入的时间或者距离不应该是负数 算法的健壮性表现在当输入数据不合法时，算 法也能做出相关处理，而不是产生异常或无法 解释的结果 可视化计算第2章 算法设计与可视化(A)9 时间效率高和存储量需求低时间效率高和存储量需求低 对于同一个问题，如果有多个算法能够达 到同样的问题解决标准，执行时间最短的 算法效率最高 存储量需求指的是算法在执行过程中需要 的最大存储空间，主要指算法程序运行时 所占用的内存或外部硬盘存储空间，越少 越好 可视化计算第2章 算法设计与

5、可视化(A)10 算法效率的度量 一个用高级程序语言编写的程序在计算机 上运行时所消耗的时间取决于下列因素： 编译产生的代码质量； 算法采用的策略、方法； 问题的输入规模； 机器执行指令的速度。 可视化计算第2章 算法设计与可视化(A)11 一个完全数算法 在RAPTOR中，一个算法的 执行语句的次数，可以通 过估算，统计出来 RAPTOR自身，也可以统计 计算过程中，含有表达式 的语句的执行次数 （1014070 symbols evaluated） 可视化计算第2章 算法设计与可视化(A)12 测定运行时间的可靠方法 RAPTOR计算对运行时间有消耗的基本符号 的执行次数 算法运行时间与这

6、个计数值成正比 这个执行次数可以与估算的次数相互印证 和比对 可视化计算第2章 算法设计与可视化(A)13 算法的效率分析的客观性 算法的效率分析可以独立于所实现的语言 和计算机 所关心的是算法设计中所考虑的策略 甚至可以忽略数据的输入与输出等次要环 节上的时间花费，关注主要算法逻辑上的 设计思路与合理性 可视化计算第2章 算法设计与可视化(A)14 算法复杂度算法复杂度 判断一个算法的优劣，只通过少量的数据 是不能做出准确判断的 根据算法案例的分析和实验可以发现，通 过比对针对同一问题的几个不同算法的关 键执行次数函数的渐近增长性，基本就可 以分析出： 某个算法，随着n的增大，它会越来越优于

7、另一 算法 或者越来越逊色于另一算法 可视化计算第2章 算法设计与可视化(A)15 函数的渐近增长 常见的算法求解问题的输入量被称为问题 的规模(Size)，一般用一个整数表示 搜索问题的规模是线性表或集合的大小 矩阵乘积问题的规模是矩阵的阶数 而图论问题的规模则是图中的顶点数或边数 指给定两个函数f（n）和g（n） 如果存在一个整数N，当n N时，所有的f（n）都大 于g（n），那么，我们说f（n）的渐近增长快于g（n） 可视化计算第2章 算法设计与可视化(A)16 算法时间复杂度 进行算法分析时，语句总的执行次数T（n） 是关于问题规模n的函数，进而分析T（n） 随n的变化情况并确定T（n

8、）的数量级 算法的时间复杂度，也就是算法的时间量 度，记作： T（n）= O(f(n) 可视化计算第2章 算法设计与可视化(A)17 常见算法复杂度 执行次数的函数执行次数的函数阶阶非正式术语非正式术语 12O(1)常数阶 2n+3O(n)线形阶 3n2+2n+1O(n2)平方阶 5log2n+20O(logn)对数阶 6n3+2n2+3n=4O(n3)立方阶 2nO(2n)指数阶 这样用大写O( )来体现算法时间复杂度的记法， 称之为大O记法(Big O notation)。 一般情况下，随着n的增大，T(n)增长最慢的算 法为最优算法 可视化计算第2章 算法设计与可视化(A)18 可行的算

9、法复杂度 常用的时间复杂度所耗费的时间从小到大 依次是： O(1) O(logn) O(n) O(nO(1) O(logn) O(n) O(n2 2) O(n) O(n3 3) O(2) O(2n n)O(n!)O(n)O(n!)O(nn n) ) 算法设计中，O(n) 、O(n2) 等最为常见 O(1) 、O(logn) 则是设计优良的算法 O(n3)等过大的n都会使得算法的实现变得不现实 O(2n)和O(n!)等除非是很小的n值，若n=100，try it？ 可视化计算第2章 算法设计与可视化(A)19 算法比较 假设算法需要N个数据值来处理。 如果每个操作执行时间为1s，运行100个 数

10、据值的算法用多少微秒 1s（微秒）= 1百万分之一秒 算法的计算次数为： 可视化计算第2章 算法设计与可视化(A)20 算法比较 在已知的宇宙中的质子数在已知的宇宙中的质子数1079 宇宙大爆炸以来的微秒数宇宙大爆炸以来的微秒数1024 可视化计算第2章 算法设计与可视化(A)21 推算大O阶方法 用常数1取代运行时间中的所有加法常数 在修改后的运行次数函数中，只保留最高 阶项 如果最高阶项存在并且不是1，则去除与这 个项相乘的常数。得到的结果就是大O阶 可视化计算第2章 算法设计与可视化(A)22 常数阶常数阶 一般指顺序结构算法的时间复杂度 注意：不管顺序结构算法的语句有多长，我们 都记作

11、O(1) 对于分支结构而言，无论决策语句判断的 结果是真，还是假，执行的次数都是恒定 的，所以单纯的分支结构，其时间复杂度 也是O(1) 例如，某些哈希查找过程是一个常数阶的运算 可视化计算第2章 算法设计与可视化(A)23 常数阶常数阶图示图示 可视化计算第2章 算法设计与可视化(A)24 线性阶线性阶 线性阶一般来自循环结构。要确定某个算 法的阶次，常常需要确定某个特定语句或 某个语句集运行的次数 例如，对于无序数列进行的关键字查找是一个 线性阶的过程，时间复杂性与数列的长度成正 比 可视化计算第2章 算法设计与可视化(A)25 线性阶线性阶图示图示 可视化计算第2章 算法设计与可视化(A

12、)26 平方阶平方阶 通常来自循环嵌套，它的内循环在前面已 经分析过，时间复杂度为O(n) 而对于外层的循环，不过是对内部的时间复杂 度为O(n)的语句，再循环n次。所以这段代码的 时间复杂度为O(n2) 如果外循环的循环次数改为了m，时间复杂度 就变为O(mn) 可视化计算第2章 算法设计与可视化(A)27 平方阶平方阶图示图示 可视化计算第2章 算法设计与可视化(A)28 对数阶对数阶 对数阶的算法往往来自一些分治算法，例 如，折半查找，每查一次，所求解的空间 就会减少一半 而这些算法往往与有效地利用递归有关 可视化计算第2章 算法设计与可视化(A)29 对数阶对数阶图示图示 可视化计算第

13、2章 算法设计与可视化(A)30 空间复杂性的大空间复杂性的大O O阶阶 空间复杂度(Space Complexity)是对一个 算法在运行过程中临时占用存储空间临时占用存储空间大小 的量度。 注意：该空间与输入数据的规模没有关系 有的算法只需要占用少量的临时工作单元，而 且不随问题规模的大小而改变； 有的算法需要占用的临时工作单元数与解决问 题的规模n有关，它随着n的增大而增大 可视化计算第2章 算法设计与可视化(A)31 空间复杂性空间复杂性的参考案例的参考案例 一些排序方法，如快速排序的数据本身在 原地不动（in-place），运行该算法要为 递归程序执行过程所需堆栈提供辅助空间， 所以

14、是O (logn) 归并排序和基数排序需要建立新的数组来 存放排序后的数据，所需辅助空间较多， 为O(n) 在动态规划算法中，需要保存大量的算例 结果，所以其空间复杂性O(n2) 可视化计算第2章 算法设计与可视化(A)32 计算的可视化问题 如果按一般方法学习算法设计的历程，一 般需要经历程序设计、数据结构、离散数 学等课程的铺垫 引入可视化的程序设计环境，其目标则是 通过缩短现实世界中的行为与程序设计之 间的概念距离来减少学习上的认知负担 可视化计算第2章 算法设计与可视化(A)33 可视化计算 设计可视化（用连接基本图形符号来创建 算法） 运行可视化（可以选择单步执行或以连续 执行的模式

15、、可以直观地显示当前执行符 号（语句）所在的位置，以及所有变量的 内容） 结果可视化（基于Ada Graph的简单图形库， 所求解的问题的呈现和计算的结果，也是 可以是可视化的） 可视化计算第2章 算法设计与可视化(A)34 设计可视化 在编辑子程序调 用语句时， RAPTOR会自动提 示已经存在的子 程序的名称 流程图是完全可 视化的算法设计 工具 可视化计算第2章 算法设计与可视化(A)35 运行可视化 在执行过程中，目 前正在执行的符号 语句显示为绿色 所有的变量的状态 显示在屏幕左下角 的窗口中 可视化计算第2章 算法设计与可视化(A)36 调试方法 在运行程序之前，用户可使用鼠标右键

16、单 击任何语句，调出菜单选择“Toggle Breakpoint”选项，设置程序运行的断点 可以按“F10”键，单步执行语句 可视化计算第2章 算法设计与可视化(A)37 结果可视化 通过主控制台（Master Console）输出文 字性的计算结果和表达式运行计数值 可视化计算第2章 算法设计与可视化(A)38 结果可视化 一些计算问题和结果，如迷宫、棋盘甚至 三维立体图形都可以通过图形界面输出 可视化计算第2章 算法设计与可视化(A)39 RAPTOR与流程图规范 由于RAPTOR设计考虑了程序设计初学者的 因素，一些特殊设计与传统的流程图有差 异 所以： RAPTOR 流程图 可视化计算第2章 算法设计与可视化(A)40 认识RAPTOR 流程图 了解和认识正式的流程图规范，以便在书 面应用中不至于出现与标准冲突的问题 了解RAPTOR的特殊性，以便借鉴来从其他 文献的流程图算法，进行比对和移植 深入了解RAPTOR以后，可以方便的从其他 高级语言编制的算法中，进行移植和使用 可视化方法验证算法 可视化计算第2章 算法设计与可视化(A)41 RAPTOR与流程图规范的差异 RAPTOR使用的流程图符号较规范中的少且 有差异； 可视化计算第2章 算法设计与可视化(A)42 RAPTOR与流程图规范的差异 RAPTOR流程 图中循环语 句的决策出 口