《计算机程序设计基础课程教学pptfop11》由会员分享，可在线阅读，更多相关《计算机程序设计基础课程教学pptfop11（71页珍藏版）》请在金锄头文库上搜索。
1、乔 林,计算机程序设计基础,Email: Tel: 62780973,清华大学计算机科学与技术系,第十一章 算法设计与分析,学习目标 了解大多数问题都可以用几种不同的算法解决 掌握什么样的算法是正确的 了解解决同一问题的不同算法其性能各不相同 了解算法复杂度的概念，用它可对随着问题规模成比例增长的运行时间的变化作定性分析 学会用大“O”符号表示算法复杂度；掌握最常见的复杂度类型，并且理解每个复杂度类型的性能特点,11.1 算法的概念与特征,算法的由来 解决问题的方法与步骤 演算过程的抽象表述 算法的基本特征 有穷性：算法必须能够在有限步内终止 确定性：每一步骤的顺序和内容不能有二义性 有效性
2、：所有操作都有明确含义并能够实现 有零个或多个输入：算法应该接受处理数据 有一个或多个输出：算法必须能够输出结果,正确性不是算法的特征，算法的正确性由设计者保证！,算法举例一,33 幻方 用数字19组成33方阵，各行各列各对角线的数字之和为15 算法步骤 S1：把1放在第一行中间的一格 S2：在右上方斜对角线方向给出下一个自然数 在此过程中，若该数已出方框，则将其写在该行或该列另一端 S3：写完三个数后，将第四个数写在第三个数下 S4：重复上述操作， 直到格子填满为止,算法举例一,算法举例一,算法举例一,算法举例一,算法举例一,算法举例一,算法举例一,算法举例一,算法举例一,算法举例一,算法举
3、例一,算法举例一,算法举例一,算法举例一,算法举例二,查英文词典的算法步骤 S1：翻开词典任意一页 S2：若所查词汇在本页第一个单词前，则往前翻页重复S2；若所查词汇在本页最后一个单词后，则往后翻页重复S2 S3：若非S2的情况，则依次比较本页单词，或者查出该单词，或者得出结论，查不到该单词,算法举例三,素数判定的算法步骤 S1：输入 n 的值 S2：i = 2 S3：r = n / i S4：若 r = 0，则 n 不是素数，结束；若 r 0 ，执行S5 S5：i = i + 1 S6：若 i n 1，返回S3；否则判定 n 为素数，结束,11.2 算法的类型与结构,数值算法与非数值算法 算
4、法的基本结构 顺序结构 分支结构 循环结构 程序的结构化,11.3 算法的描述方法,流程图 使用流线表示程序控制流 程序逻辑清晰，绘制复杂 N-S图 去除流线与箭头的流程图 绘制复杂，逻辑不清晰 伪代码 程序逻辑较不清晰，书写简单,11.4 算法的设计与实现,算法实现过程 问题分析 按某种策略实现算法 验证上述实现确实为算法 证明算法的正确性 选择合适的策略，提高算法效率,素数判定问题,函数原型 int IsPrime( int n ); 素数判定问题的第二种算法 检查 1 到 n 的数中，是否存在可被 n 整除的数 每找到一个因子，计数器自加 1 在所有数判断完毕后，查看计数器是否为 2 若
5、为2则为素数，否则不是,素数判定问题,int IsPrime( int n ) int divisors, i; divisors = 0; for( i = 1; i = n; i+ ) if( n % i = 0 ) divisors+; return( divisors = 2 ); ,素数判定问题,验证上述策略确为算法 操作步骤的描述清楚，不存在二义性 各操作确实可计算机实现 执行过程可终止 算法正确性的证明 素数至少有两个因子 divisors 表示数的因子个数，初始为 0，每找到一个因子，其值递增 1，循环依次查找全部 n 个自然数，若只有两个因子，显然为素数,素数判定问题,提高算
6、法效率 只要在 1 和 n 之间存在一个因子就可终止，并返回 n 不是素数 若 n 可被 2 整除，不需检验其它数，程序终止并返回 n 不是素数；若否，则所有偶数都不是因子，程序只需检验奇数 程序不必检验因子一直到 n，只需到 即可,素数判定问题,int IsPrime( int n ) int i; if( n % 2 = 0 ) return 0; for( i = 3; i = sqrt(n); i += 2 ) if( n % i = 0 ) return 0; return 1; ,问题：本算法效率确实好吗？,每次迭代都需要计算平方根，很费时,素数判定问题,int IsPrime(
7、int n ) int limit, i; limit = sqrt(n); if( n % 2 = 0 ) return 0; for( i = 3; i = limit; i += 2 ) if( n % i = 0 ) return 0; return 1; ,问题：本算法确实正确吗？,浮点数的存储有误差，程序的正确性依赖机器的表示精度,素数判定问题,int IsPrime( int n ) int limit, i; limit = sqrt(n) + 1; if( n % 2 = 0 ) return 0; for( i = 3; i = limit; i += 2 ) if( n
8、% i = 0 ) return 0; return 1; ,如何选择合适的算法,选择指标 正确性 效率 可读性 可维护性 算法评估：在诸多因素中寻找平衡点 高效的算法可读性差，可读性好的算法效率一般不高,最大公约数问题,函数原型 int gcd( int x, int y); 两种算法实现策略 穷举法：逐一尝试所有可能值 欧几里德算法 步骤1：x 除以 y，余数为 r 步骤2：若 r 为 0，则 y 为所求，算法终止；否则 步骤3：将 y 作为新 x，r 作为新 y，返回第1步,最大公约数问题,穷举法实现,int gcd( int x , int y ) int g; g = x; whil
9、e( x % g != 0 | y % g != 0 ) g-; return g; ,最大公约数问题,欧几里德算法实现,int gcd( int x , int y ) int r; while( 1 ) r = x % y; if( r = 0 ) break; x = y; y = r; return y; ,11.5 算法分析与算法复杂度,算法分析的目的 评估算法的执行效率 排序算法 选择排序 归并排序 算法复杂度,选择排序,函数原型 void SortIntegerArray( int a, int n ); 基本原理 依次找最小元，将最小元与数组未排序的第一位互换 重复上述步骤,选
10、择排序,原始数组,第一趟,第二趟,选择排序,#include void SortIntergeArray( int a, int n ) int lh, rh, i, temp; for( lh = 0; lh n; lh+ ) rh = lh; for( i = lh+1; i n; i+ ) if( ai arh ) rh = i; temp = alh; alh = arh; arh = temp; void main() int i, numbers8 = 56, 25, 37, 58, 95, 19, 73, 30 ; SortIntegerArray( numbers, 8 );
11、for( i = 0; i 8; i+ ) printf( “%7d”, numbersi ); ,选择排序算法的性能分析,程序执行时间 T 随问题规模 n 显著增加 算法的主要执行时间在于循环 循环执行次数 (n2+n)/2 算法执行时间的估计与测量 平方级算法执行时间：T n2,算法复杂度,算法复杂度的定义 算法的执行效率随问题规模的变化趋势 算法复杂度的分类 时间复杂度：算法执行时间 空间复杂度：算法所需存储空间,大 O 表达式,算法复杂度的度量：大 O 表达式 近似描述算法的本质 例：O(n2) 表示算法复杂度与问题规模的平方近似成正比 原 则 忽略所有对变化趋势影响较小的项 忽略所有
12、常数因子 例：算法需要 2n+3n2 步骤才能完成，时间复杂度为O(2n),算法时间复杂度的估计,时间复杂度计算 total 赋值 1 次 i 赋值 1 次；i n 执行 n+1 次；i+ 执行 n 次 循环体内部代码执行 n 次 返回值执行 1 次 总计：3n+4 次；时间复杂度：O(n),double Average( double a, int n ) int i; double total; total = 0; for( i = 0; i n; i+ ) total += ai; return( total / n ); ,最高复杂度与平均复杂度,最高复杂度：算法在最坏情况下的复杂度
13、 算法复杂度的上限：无论数据如何变化，算法的复杂度都不会差于最高复杂度 平均复杂度：算法在各种数据下的复杂度平均值 算法性能的最佳估计值,最高复杂度与平均复杂度,最高时间复杂度：O(n) 最好情况：O(1) 平均时间复杂度：O(n),int LinearSearch( int key, int a, int n ) int i; for( i = 0; i n; i+ ) if( key = ai ) return i; return -1; ,归并排序,问题：选择排序复杂度与问题规模的平方成正比 问题规模增加一倍，时间消耗变为 4 倍 问题规模减为一半，时间消耗减为 分治法 思路：将原始数组
14、分成两个子数组，分别排序，然后合并 只要数组合并的时间小于排序算法的时间，分治法就是有效的,归并排序,原始数组,数组分解,归并排序,原始数组,子数组排序,归并排序,原始数组,子数组排序（问题：子数组如何排序？）,子数组归并,归并排序,子数组归并,归并排序,子数组归并,归并排序,子数组归并,归并排序,子数组归并,归并排序,子数组归并,归并排序,算法描述 判断数组是否为空或者只有单个元素。若是，则相当于已排序，函数直接返回。否则 将该数组分割为两个子数组，每个子数组大小都是原数组的一半左右 使用同样的方法排序两个子数组 合并两个已排序的子数组 函数原型 void SortIntegerArray(
15、 int a, int low, int high ); void Merge( int a, int low, int mid, int high );,归并排序,void SortIntegerArray( int a, int low, int high ) int i, tmp, mid; if( high = low + 1 ) / only two numbers if( ahigh low + 1 ) / more than two numbers mid = ( high + low ) / 2; / divide into two subarrays SortIntegerA
16、rray( a, low, mid ); / sort them respectively SortIntegerArray( a, mid+1, high ); Merge( a, low, mid, high ); / merge them ,归并排序,void Merge( int a, int low, int mid, int high ) int i, m, n; int *p, *q; p = ( int* )malloc( sizeof( int ) * ( high - low + 1 ) ); m = low; n = mid + 1; q = p; while( m = mid ,归并排序,算法复杂度：归并排序的
