课程介绍分析.pptVIP

sss 计算这程序段的程序步数，可转化为计算关键操作 　　　　c[i][j] += a[i][k] * b[k][j]; 的执行频数。找出执行频数与n 的函数关系： f(n) = n3 则渐近时间复杂度 T(n) = O(n3) 第1讲 算法分析 例题2：分析冒泡排序算法的渐近时间复杂度 void bubble_sort(int a[ ], int n){ int i, j, t, change; for(i=n-1, change=1; i1 change; --i) change = 0; for(j=0; ji; ++j) if(a[j] a[j+1]) { t=a[j]; a[j]=a[j+1]; a[j+1]=t; change=1; } } 将“交换序列中相邻两个整数”作为关键操作，计算其执行频数。 若a[ ] 为自小至大有序，则执行频数为0； 若a[ ] 自大至小排列，则执行频数为n(n-1)/2。 即 f(n) = n(n-1)/2； 所以， 渐近时间复杂度为 T(n) = O(n2) 第1讲 算法分析 √本章小结 理解算法定义、要素、性质、特征 算法设计方法 算法描述方法 算法实现工具 算法分析方法 第1讲 算法概述 √本章课程学习任务 （1）购买教材 （2）快速阅读理解第1章12-34页内容 （3）预习第2章内容 思考题：如何理解算法、数据、程序之间的区别和联系？ 第1讲 算法概述 That’s all for today See you next time Good bye! * * * * * 计算机科学学院 王小明 （博士/教授/博士生导师） Email: wangxm@snnu.edu.cn 陕西师范大学 算法设计与分析 （本科专业选修课） √课程属性：专业选修课 √课程课时：约54学时（1-19周） √上课时间：周三（单、双周，5-6节）14：30–16：20 教室：文渊楼 201 周四（单周，7-8节）16：40–18：30 教室：文渊楼 201 课程简介(1) 本科生选修课 算法分析与设计 √教师简介： 王小明，博士，教授，博士生导师，2007年至2008年留学美国，访问学者。 中国计算机学会高级会员，开放与并行专委会委员，陕西省计算机学 会理事 研究方向：无线自组织网络，系统安全，复杂系统建模与仿真, 智能算法。 √课程助教：张峰（博士），蒋丽萍（博士），曹玉林（博士） 鲁天龙（硕士） 袁辉辉（硕士）吴三柱（硕士），张珊珊（硕士） 课程简介(1) 本科生选修课 算法分析与设计 √课程教材：算法设计与分析(第2版)， 吕国英 主编， 任瑞征，钱宇华 参编 清华大学出版社，2009年1月（共294页） 课程简介(2) √参考教材： 算法设计与分析，王晓东 编著 清华大学出版社，2007年8月（共396页） 算法设计与分析习题解答(第2版)， 王晓东 编著 清华大学出版社，2008年2月 课程简介(3) √参考教材：算法设计与分析，耿国华 主编 高等教育出版社，2012年1月 （共244页） √参考教材：算法设计，Jon Kleinberg 等 著，张立昂，屈婉玲 译 清华大学出版社，2007年1月 （共573页） √参考教材：大学算法教程，Richard Johnsonbaugh 等 著，方存正 等 译 清华大学出版社，2007年6月 （共610页） √参考教材：计算机算法导引，卢开澄 编著 清华大学出版社， 2006年6月 （共412页） 课程简介(4) √期终考核： 平时作业成绩 30% 小论文(包括算法、程序、上机实验结果) 20% 笔试成绩 50% √上课形式： 【1】讲授 + 答疑 + 作业辅导 + 上机实验