乔林.ppt
《乔林.ppt》由会员分享,可在线阅读,更多相关《乔林.ppt(71页珍藏版)》请在三一文库上搜索。
1、乔 林,计算机程序设计基础,Email: Tel: 62792961,第十一章 算法设计与分析,学习目标 了解大多数问题都可以用几种不同的算法解决 掌握什么样的算法是正确的 了解解决同一问题的不同算法其性能各不相同 了解算法复杂度的概念,用它可对随着问题规模成比例增长的运行时间的变化作定性分析 学会用大“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 若为2则为素数,否则不是,素数
5、判定问题,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 个自然数,若只有两个因子,显然为素数,素数判定问题,提高算法效率 只要在 1 和 n
6、之间存在一个因子就可终止,并返回 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( int n ) int li
7、mit, 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 % i = 0 ) retu
8、rn 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; while( x % g != 0
9、| 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 ); for( i = 0; i
11、8; i+ ) printf( “%7d”, numbersi ); ,选择排序算法的性能分析,程序执行时间 T 随问题规模 n 显著增加 算法的主要执行时间在于循环 循环执行次数 (n2+n)/2 算法执行时间的估计与测量 平方级算法执行时间:T n2,算法复杂度,算法复杂度的定义 算法的执行效率随问题规模的变化趋势 算法复杂度的分类 时间复杂度:算法执行时间 空间复杂度:算法所需存储空间,大 O 表达式,算法复杂度的度量:大 O 表达式 近似描述算法的本质 例:O(n2) 表示算法复杂度与问题规模的平方近似成正比 原 则 忽略所有对变化趋势影响较小的项 忽略所有常数因子 例:算法需要 2n
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 乔林
链接地址:https://www.31doc.com/p-2578443.html