中科院陈玉福算法课件ch1ppt

计算机算法设计与分析 The Design and Analysis of Computer Algorithms
中国科学院研究生院 陈玉福
关于计算机算法
计算机科学 是一种创造性思维活动，其教育必须面向设计； 计算机算法 是任何定义好了的计算程式，它取某些值或值 的集合作为输入，并产生某些值或值的集合作为输出。 计算机算法的特征 – 数据输入与输出； – 确定性： 算法的每一步计算（包括判断）必须要有确切 的定义，即每一步计算动作必须是清楚的，无二义性。
空间复杂性
考虑空间复杂性的理由
在多用户系统中运行时，需指明分配给该程序的内存 大小； 想预先知道计算机系统是否有足够的内存来运行该程 序； 用空间复杂性来估计一个程序可能解决的问题的最大 规模； 一个问题可能有若干个不同的内存需求解决方案，从 中择优。
指令空间: 存储编译后的程序指令
指令空间的大小取决于如下因素： 把程序编译成机器代码的编译器，编译器不同，则产 生的机器代码的长度就会有差异； 编译时实际采用的编译器选项，如优化模式、覆盖模 式，选用优化模式可缩短代码长度，但会增加运行时 间； 目标计算机的配置，如带有浮点处理硬件的，每个浮 点操作转换为一条机器指令，否则，必须生成仿真的 浮点计算代码，使整个机器代码加长。 一般情况下，指令空间对于所解决的特定问题不够敏 感。
– 可实现性：每种计算至少在原理上能由人用纸和笔在有
限的时间内完成。 – 有穷性： 一个算法总是在执行了有穷步之后终止。
关于算法设计与分析
如何设计算法：问题的数学模型、经典算法、分析改进。 如何表示算法：输入数据结构、描述算法的语言、算法 流程、逻辑结构。C++ 或 ALGEN（伪代码）。 如何分析算法：发现算法特性、估计对各种应用的适合 程度、相同应用中与其它算法的比较。确定输入数 据模型、确定每项基本操作所用时间及出现频率、 统计数据、分析推求。 如何测试算法：正确性、有穷性；白盒法、黑盒法。
时间复杂性
考虑时间复杂性的理由
某些计算机用户需要提供程序运行时间的上限 （用户可接受的）； 所开发的程序需要提供一个满意的实时反应； 把握问题求解的难易程度； 比较算法的优劣，改进算法。
时间复杂度的构成
Borland C++基本数据类型（32位字长机器）
类型名 char unsigned char pointer short [int] signed short [int] unsigned short [int] int signed [int] unsigned [int] long [int] signed long [int] unsigned long [int] float double long double 字符型 无符号字符型 指针型 短整型 有符号短整型 无符号短整型 整型 有符号整型 无符号整型 长整型 有符号长整型 无符号长整型 单精度浮点型 双精度浮点型 长双精度浮点型 说明 字节数 1 1 2 2 2 2 4 4 4 4 4 4 4 8 16 -32768~32767 -32768~32767 0~65535 -2147483648~ 2147483647 -2147483648~ 2147483647 0~4294967295 -2147483648~ 2147483647 -2147483648~ 2147483647 0~4294967295 ±3.4E ±38 ±1.7E ±308 -3.4E-4932~ 1.1E+4932 使用范围 -128~127 0~255
环境栈空间：保存函数调用返回时恢复运 行所需要的信息
返回地址； 所有局部变量的值； 递归函数的传值形式参数的值； 所有引用参数及常量引用参数的定义。 Rsum(a,n) Rsum(a,n-1) ……………. Rsum(a,1) Rsum(a,0)
数值求和的例子
template<class T> T Sum( T,a[ ], int n ) {//计算 a[0:n-1]的和 T tsum=0; for(int i=0, i<n; i++) tsum+=a[i]; return tsum; } 存数组的地址a, 变量n, i, tsum: Sc=2+4+4+sizeof(T) template<class T> T Rsum( T a[ ], int n) {//计算a[0:n-1]的和 if (n>0) return Rsum(a,n-1)+a[n-1]; return 0; } 保留a的地址，函数返回地址， 存储变量n , 递归深度为 n+1 Sv=(2+2+4)(n+1)
考核
40学时/2学分 平时20% , 出席、作业 期末80%, 课堂开卷
联系： yfchen@
第一章 复杂性分析初步
计算复杂性的本质是研究完善的模型，在这样的模型 范围内可以评估重要问题的固有困难，并得以进一步 研究“有效的”算法。对于许多重要问题，已知算法的 复杂度在最坏情形下的渐近下界和上界之间存在显著 的差距。计算复杂性研究能够在探索这些问题的新算 法方面提供指导。 计算复杂性体现在算法占用机器空间资源和时间资源 的情况，是关于选定模型下输入数据规模的函数。起 决定作用的是这些函数当输入数据规模趋于无穷大时 的渐进性态。 一种输入数据模型的选用可能使复杂性分析更简单， 而另一种输入模型可能更好地反映程序将被使用的情 况。
数据空间：存储所有常量和变量的值
存储常量和简单变量：所需的空间取决于所使用 的计算机和编译器,以及变量与常量的数目； 存储复合变量：包括数据结构所需的空间及动态 分配的空间； 计算方法：复合变量所占空间等于各个成员所占 空间的累加。 例如：数组变量所占空间等于数组大小乘以单个 数组元素所占的空间。 double a[100]; 所需空间为100×8＝800 int matrix[r][c]; 所需空间为 4×r×c
教学要求
教学内容
复杂性分析初步 图与遍历算法 分治算法 贪心算法 动态规划算法 回溯算计算机算法基础》，华中理 工大学出版社，2005。 Alfred V. Aho 等，《计算机算法的设计与 分析》（ 英文影印版），机械工业出版 社，2006。 S. Baase, A. Van Gelder ，《COMPUTER ALGORITHMS-Introduction to Design and Analysis》,Third Edition, Higher Education Press,2001. Cormen，T.H. 等，《算法导论》，高等教 育出版社，2001。 王晓东，《计算机算法设计与分析》，电 子工业出版社，2001。