1、xxx算法设计与分析算法设计与分析辽宁师范大学计算机与信息技术学院辽宁师范大学计算机与信息技术学院计算机科学与技术专业课程计算机科学与技术专业课程Algorithm Design and AnalysisAlgorithm Design and Analysis辽辽宁宁师师范大范大学计学计算机算机与与信息技信息技术学术学院院 宋宋传鸣传鸣算法算法设计与设计与分析分析概述概述关于任课教师关于任课教师课程介绍课程介绍什么是算法什么是算法算法的描述算法的描述算法分析算法分析宋传鸣宋传鸣 讲师讲师u2003年本科毕业于辽宁师范大学计算机科学与技年本科毕业于辽宁师范大学计算机科学与技术系计算机应用技术专
2、业术系计算机应用技术专业,工学学士工学学士u2006年硕士毕业于辽宁师范大学计算机科学与技年硕士毕业于辽宁师范大学计算机科学与技术系计算机应用技术专业术系计算机应用技术专业,工学硕士工学硕士u2010年博士毕业于南京大学计算机科学与技术系年博士毕业于南京大学计算机科学与技术系计算机应用技术专业计算机应用技术专业,工学博士工学博士u2010年年7月回校任教至今月回校任教至今联系方式联系方式u电子邮件电子邮件: u办公室办公室:西山校区第二教学楼西山校区第二教学楼B614 u个人主页个人主页:辽辽宁宁师师范大范大学计学计算机算机与与信息技信息技术学术学院院 宋宋传鸣传鸣算法算法设计与设计与分析分析
3、概述概述关于关于算法设计与分析算法设计与分析课程课程课程介绍课程介绍什么是算法什么是算法算法的描述算法的描述算法分析算法分析课程性质课程性质u本课程属于专业选修课本课程属于专业选修课(计算机科学与技术计算机科学与技术)、专、专业必修课业必修课(计算机科学与技术计算机科学与技术(动画动画)开设目的开设目的u使学生掌握非数值算法设计的主要方法使学生掌握非数值算法设计的主要方法 u独立设计算法和对算法进行复杂性计算奠定基础独立设计算法和对算法进行复杂性计算奠定基础 u利用所学的算法设计策略解决实际问题的能力利用所学的算法设计策略解决实际问题的能力 学时安排学时安排u48学时学时,每周每周3学时学时,
4、修完课程可获修完课程可获3学分学分u考核方式考核方式考察考察u期末为闭卷笔试期末为闭卷笔试,成绩占总成绩的成绩占总成绩的50%u平时出勤占平时出勤占5%,学期论文学期论文(3篇篇)占占45%(第第4/8/12周周)u试卷题型试卷题型:概念型、设计型、证明型概念型、设计型、证明型辽辽宁宁师师范大范大学计学计算机算机与与信息技信息技术学术学院院 宋宋传鸣传鸣算法算法设计与设计与分析分析概述概述关于关于算法设计与分析算法设计与分析课程课程课程介绍课程介绍什么是算法什么是算法算法的描述算法的描述算法分析算法分析在专业教学计划中的地位和作用在专业教学计划中的地位和作用 u在在IEEE ACM 公布的公布
5、的Computer Science Curriculum 2008与中国计算机学会教育委员会、全与中国计算机学会教育委员会、全国高等学校计算机教育研究会推出的国高等学校计算机教育研究会推出的CCC 2004 (China Computing Curricula 2004-CS)中中,算法设算法设计与分析都是其计与分析都是其核心课程核心课程之一之一u算法设计与分析具有学科核心的重要地位算法设计与分析具有学科核心的重要地位,能够能够充分体现计算机科学方法论的理论、抽象和设计充分体现计算机科学方法论的理论、抽象和设计3个过程个过程,知识面较宽知识面较宽,有一定的深度有一定的深度 u反复再现反复再现计
6、算机科学中用到的典型问题的复杂性、计算机科学中用到的典型问题的复杂性、效率、抽象的层次、重用、折衷等带有效率、抽象的层次、重用、折衷等带有普遍性的普遍性的概念概念 u不仅是计算机科学与技术专业后续课程的理论基不仅是计算机科学与技术专业后续课程的理论基础础,而且还而且还广泛地用于新兴的技术和研究领域广泛地用于新兴的技术和研究领域 辽辽宁宁师师范大范大学计学计算机算机与与信息技信息技术学术学院院 宋宋传鸣传鸣算法算法设计与设计与分析分析概述概述关于关于算法设计与分析算法设计与分析课程课程课程介绍课程介绍什么是算法什么是算法算法的描述算法的描述算法分析算法分析计算思维计算思维(Computation
7、al Thinking) u摘自摘自中国计算机学会通讯中国计算机学会通讯2012年第一期年第一期u理论科学、实验科学、理论科学、实验科学、计算科学计算科学被称为推动人类被称为推动人类文明进步和科技发展的三大科学文明进步和科技发展的三大科学u科学思维包括理论思维、实验思维和计算思维科学思维包括理论思维、实验思维和计算思维p理论思维理论思维以推理和演绎为特征以推理和演绎为特征,如数学学科如数学学科p实验思维实验思维以观察和总结自然规律为特征以观察和总结自然规律为特征,如物如物理学科理学科p计算思维计算思维以设计和构造为特征以设计和构造为特征,如计算机学科如计算机学科u计算思维是运用计算的基础概念去
8、求解问题、设计算思维是运用计算的基础概念去求解问题、设计系统和理解人类行为的一种方法计系统和理解人类行为的一种方法.它合用了数学它合用了数学思维思维(求解问题的方法求解问题的方法)、工程思维、工程思维(设计、评价大设计、评价大型复杂系统型复杂系统)和科学思维和科学思维(理解可计算性、智能、理解可计算性、智能、心理和人类行为心理和人类行为)u计算思维课程现已在部分高校中开启计算思维课程现已在部分高校中开启辽辽宁宁师师范大范大学计学计算机算机与与信息技信息技术学术学院院 宋宋传鸣传鸣算法算法设计与设计与分析分析概述概述教材教材(Textbook)(Textbook)课程介绍课程介绍什么是算法什么是
9、算法算法的描述算法的描述算法分析算法分析王晓东编著王晓东编著.计算机算法设计与分析计算机算法设计与分析(第第3版版). 北北京京:电子工业出版社电子工业出版社, 2007. 辽辽宁宁师师范大范大学计学计算机算机与与信息技信息技术学术学院院 宋宋传鸣传鸣算法算法设计与设计与分析分析概述概述主要参考书主要参考书(References)(References)课程介绍课程介绍什么是算法什么是算法算法的描述算法的描述算法分析算法分析M. H. Alsuwaiyel著著,吴伟昶吴伟昶,方世昌译方世昌译.算法设计算法设计技巧与分析技巧与分析. 北京北京:电子工业出版社电子工业出版社, 2010.Thoma
10、s H. Cormer等著等著, 潘金贵潘金贵, 顾铁成等译顾铁成等译. 算算法导论法导论(第二版第二版). 北京北京: 机械工业出版社机械工业出版社, 2010 辽辽宁宁师师范大范大学计学计算机算机与与信息技信息技术学术学院院 宋宋传鸣传鸣算法算法设计与设计与分析分析概述概述主要参考书主要参考书(References)(References)课程介绍课程介绍什么是算法什么是算法算法的描述算法的描述算法分析算法分析The Art of Computer Programming数据结构的开拓者数据结构的开拓者D.E.Knuth的计算机科学发展的计算机科学发展史上的不朽之作史上的不朽之作u第第1卷
11、卷 基本算法基本算法:介绍计算机程序设计的基本算法介绍计算机程序设计的基本算法,包括基本的编程概念和技术以及信息结构包括基本的编程概念和技术以及信息结构-机内机内信息的表示、数据元及其处理的结构关系信息的表示、数据元及其处理的结构关系u第第2卷卷 半数值算法半数值算法:介绍随机数和算术介绍随机数和算术,提供了计提供了计算机编程和数值分析之间的丰富接口算机编程和数值分析之间的丰富接口u第第3卷卷 排序与查找排序与查找:介绍排序和查找的最权威的经介绍排序和查找的最权威的经典技术典技术,扩充了第扩充了第1卷的数据结构卷的数据结构,以处理大小型数以处理大小型数据库及内外部存储据库及内外部存储.本书偏重
12、分析技术本书偏重分析技术,采用汇编采用汇编语言描述算法语言描述算法,是一本本学科最经典最权威的百是一本本学科最经典最权威的百科全书科全书,适合于从事数据结构与算法研究的专家适合于从事数据结构与算法研究的专家阅读阅读辽辽宁宁师师范大范大学计学计算机算机与与信息技信息技术学术学院院 宋宋传鸣传鸣算法算法设计与设计与分析分析概述概述算法设计与分析算法设计与分析课程的主要内容课程的主要内容课程介绍课程介绍什么是算法什么是算法算法的描述算法的描述算法分析算法分析第一章第一章 绪论绪论第二章第二章 数学预备知识与典型的数据结构数学预备知识与典型的数据结构 第三章第三章 递归与分治策略递归与分治策略 第四章
13、第四章 动态规划动态规划第五章第五章 贪心算法贪心算法 第六章第六章 NP完全问题完全问题第七章第七章 回溯法回溯法第八章第八章 分支限界法分支限界法第九章第九章 随机化算法随机化算法 第十章第十章 网络流算法网络流算法第十一章第十一章 并行算法入门并行算法入门辽辽宁宁师师范大范大学计学计算机算机与与信息技信息技术学术学院院 宋宋传鸣传鸣算法算法设计与设计与分析分析概述概述算法设计与分析算法设计与分析课程的基本要求课程的基本要求课程介绍课程介绍什么是算法什么是算法算法的描述算法的描述算法分析算法分析培养学习方法与习惯培养学习方法与习惯u上课记笔记上课记笔记u阅读与自学阅读与自学u理论联系实际理
14、论联系实际u查找资料查找资料课上认真听讲课上认真听讲,课后多思考多翻阅资料课后多思考多翻阅资料辽辽宁宁师师范大范大学计学计算机算机与与信息技信息技术学术学院院 宋宋传鸣传鸣算法算法设计与设计与分析分析概述概述关于理论计算机科学关于理论计算机科学课程介绍课程介绍什么是算法什么是算法算法的描述算法的描述算法分析算法分析关于计算机和计算机械的数学理论关于计算机和计算机械的数学理论,也称也称计算理论计算理论u自动机与形式语言理论自动机与形式语言理论u程序理论程序理论u形式语义学形式语义学u算法分析和计算复杂性理论算法分析和计算复杂性理论学科产生学科产生u20世纪世纪30年代年代,人们关注是否存在一种有
15、效过程求人们关注是否存在一种有效过程求解问题解问题,即即问题的可解问题的可解与与不可解性不可解性u如果存在某个模型能够建立一个算法求解问题如果存在某个模型能够建立一个算法求解问题,则则将该问题归入可解的问题类将该问题归入可解的问题类u30年代前期年代前期,哥德尔等创立递归函数哥德尔等创立递归函数u30年代中期年代中期,丘奇的丘奇的演算演算,波斯特的波斯特机波斯特的波斯特机,图图灵的图灵机灵的图灵机u40年代后期年代后期:存储程序型计算机存储程序型计算机(RAM,RASPM)辽辽宁宁师师范大范大学计学计算机算机与与信息技信息技术学术学院院 宋宋传鸣传鸣算法算法设计与设计与分析分析概述概述算法分析
16、与计算复杂性理论算法分析与计算复杂性理论课程介绍课程介绍什么是算法什么是算法算法的描述算法的描述算法分析算法分析各类具体算法的复杂性的研究称作各类具体算法的复杂性的研究称作算法分析算法分析一般算法的复杂性的研究称作一般算法的复杂性的研究称作计算机复杂性理论计算机复杂性理论计算复杂性理论原是可计算理论的一支计算复杂性理论原是可计算理论的一支,是是以各种以各种可计算函数可计算函数(递归函数递归函数)的计算复杂性为研究对象的计算复杂性为研究对象基本问题基本问题u实际可计算函数的结构和性质实际可计算函数的结构和性质p60年代中期以来年代中期以来,有关研究者一般以计算时间有关研究者一般以计算时间多项式有
17、界的函数作为实际可计算的函数多项式有界的函数作为实际可计算的函数u确定性机器与非确定性机器的解题能力比较确定性机器与非确定性机器的解题能力比较关于计算和算法的研究关于计算和算法的研究u对串行计算的性质研究多对串行计算的性质研究多u对对并行计算性质的研究少并行计算性质的研究少辽辽宁宁师师范大范大学计学计算机算机与与信息技信息技术学术学院院 宋宋传鸣传鸣算法算法设计与设计与分析分析概述概述算法算法(Algorithm)(Algorithm)的定义的定义课程介绍课程介绍什么是算法什么是算法算法的描述算法的描述算法分析算法分析解决问题的一种方法或过程解决问题的一种方法或过程,由若干条指令组成由若干条指
18、令组成uAlgorithm一词源于公元九世纪的一位波斯数学家一词源于公元九世纪的一位波斯数学家 Muhammad ibn Musa al-Khwarizmi的书的书u示例示例:给定正数给定正数m和和n,找出两个数的最大公约数找出两个数的最大公约数pE1. 用用n除以除以m,并令并令r为余数为余数(0rn)pE2. 如果如果r=0,则算法结束则算法结束, n为所求为所求pE3. 令令m=n, n=r,转入转入E1.算法的性质算法的性质u输入输入:有零个或多个由外部提供的量有零个或多个由外部提供的量u输出输出:至多一个量作为输出至多一个量作为输出u确定性确定性:每条指令是清晰的每条指令是清晰的,无
19、歧义的无歧义的u有限性有限性:每条指令执行次数有限每条指令执行次数有限,执行时间也有限执行时间也有限u有效性有效性:每个操作须使用户利用纸笔在有限时间内每个操作须使用户利用纸笔在有限时间内精确地完成精确地完成辽辽宁宁师师范大范大学计学计算机算机与与信息技信息技术学术学院院 宋宋传鸣传鸣算法算法设计与设计与分析分析概述概述求解问题的一般过程求解问题的一般过程课程介绍课程介绍什么是算法什么是算法算法的描述算法的描述算法分析算法分析辽辽宁宁师师范大范大学计学计算机算机与与信息技信息技术学术学院院 宋宋传鸣传鸣算法算法设计与设计与分析分析概述概述算法与程序算法与程序课程介绍课程介绍什么是算法什么是算法
20、算法的描述算法的描述算法分析算法分析算法与程序的区别算法与程序的区别u程序是算法用某种程序设计语言的具体实现程序是算法用某种程序设计语言的具体实现u程序可以不满足算法的第四条性质程序可以不满足算法的第四条性质为什么要学习算法？为什么要学习算法？u算法是程序的灵魂算法是程序的灵魂p问题求解过程问题求解过程:分析问题分析问题设计算法设计算法编写程编写程序序整理结果整理结果p程序设计研究的四个层次程序设计研究的四个层次:算法算法方法学方法学语语言言工具工具u提高分析问题的能力提高分析问题的能力p算法的形式化算法的形式化思维的逻辑性和条理性思维的逻辑性和条理性辽辽宁宁师师范大范大学计学计算机算机与与信
21、息技信息技术学术学院院 宋宋传鸣传鸣算法算法设计与设计与分析分析概述概述算法可以解决哪些类型的问题算法可以解决哪些类型的问题? ?课程介绍课程介绍什么是算法什么是算法算法的描述算法的描述算法分析算法分析问题的特点问题的特点有很多候选的解决方案有很多候选的解决方案,而要找出其中真正需要的而要找出其中真正需要的方案并不容易的情况方案并不容易的情况有着实际应用背景有着实际应用背景,但是受到经济利益但是受到经济利益,运行成本等运行成本等多方面的限制多方面的限制算法应用举例算法应用举例u人类基因组项目人类基因组项目:找出人类找出人类DNA中所有中所有100000种基种基因因,确定构成人类确定构成人类DN
22、A的的30亿种化学基对的各种序亿种化学基对的各种序列列,并将信息存储并将信息存储,检索和分析等检索和分析等u互联网互联网:寻找合理的数据传输路径寻找合理的数据传输路径u电子商务电子商务:保持私人信息保持私人信息,采用公钥和数字签名等采用公钥和数字签名等u交通交通:GPS导航导航u计算几何计算几何:求解平面上求解平面上n个点的凸壳个点的凸壳u数值计算数值计算:求解求解n个矩阵相乘个矩阵相乘,解方程组等解方程组等u辽辽宁宁师师范大范大学计学计算机算机与与信息技信息技术学术学院院 宋宋传鸣传鸣算法算法设计与设计与分析分析概述概述算法可以解决哪些类型的问题算法可以解决哪些类型的问题? ?课程介绍课程介
23、绍什么是算法什么是算法算法的描述算法的描述算法分析算法分析重要的问题类型重要的问题类型查找问题查找问题排序问题排序问题图问题图问题组合问题组合问题几何问题几何问题辽辽宁宁师师范大范大学计学计算机算机与与信息技信息技术学术学院院 宋宋传鸣传鸣算法算法设计与设计与分析分析概述概述算法的描述算法的描述课程介绍课程介绍什么是算法什么是算法算法的描述算法的描述算法分析算法分析自然语言自然语言u优点优点: 容易理解容易理解u缺点缺点: 冗长冗长,有二义性有二义性u使用方法使用方法: 粗线条描述算法思想粗线条描述算法思想u注意事项注意事项: 避免写成自然段避免写成自然段流程图流程图u优点优点: 直观直观u缺
24、点缺点: 缺少严密性和灵活性缺少严密性和灵活性u使用方法使用方法: 描述简单算法描述简单算法u注意事项注意事项: 注意抽象层次注意抽象层次辽辽宁宁师师范大范大学计学计算机算机与与信息技信息技术学术学院院 宋宋传鸣传鸣算法算法设计与设计与分析分析概述概述算法的描述算法的描述课程介绍课程介绍什么是算法什么是算法算法的描述算法的描述算法分析算法分析程序设计语言程序设计语言u优点优点: 能由计算机执行能由计算机执行u缺点缺点: 抽象性差抽象性差,对语言要求高对语言要求高u使用方法使用方法: 对算法进行验证对算法进行验证u注意事项注意事项: 将算法写成子函数将算法写成子函数#include int iC
25、ommonFactor(int m, int n) int r=m%n; while(r!=0) m=n; n=r; r=m%n; return n;辽辽宁宁师师范大范大学计学计算机算机与与信息技信息技术学术学院院 宋宋传鸣传鸣算法算法设计与设计与分析分析概述概述算法的描述算法的描述课程介绍课程介绍什么是算法什么是算法算法的描述算法的描述算法分析算法分析伪代码伪代码(PseudoCode) 算法语言算法语言u介于自然语言和程序设计语言之间介于自然语言和程序设计语言之间.采用某一程序采用某一程序设计语言的基本语法设计语言的基本语法,操作指令可结合自然语言来操作指令可结合自然语言来设计设计u优点优
26、点: 表达能力强表达能力强,容易理解容易理解1. r m % n;2. 循环直到循环直到r 0 2.1 m n; 2.2 n r; 2.3 r m%n;3. 输出输出n辽辽宁宁师师范大范大学计学计算机算机与与信息技信息技术学术学院院 宋宋传鸣传鸣算法算法设计与设计与分析分析概述概述算法复杂性分析算法复杂性分析(Complexity Analysis)(Complexity Analysis)课程介绍课程介绍什么是算法什么是算法算法的描述算法的描述算法分析算法分析算法复杂性算法复杂性=算法所需要的计算机资源算法所需要的计算机资源u时间复杂性时间复杂性(Time Complexity): T=T(
27、N,I)u空间复杂性空间复杂性(Spatial Complexity): S=S(N,I)pN表示问题的规模表示问题的规模,I表示算法的输入表示算法的输入u计算机包含的运算有多种计算机包含的运算有多种,记为记为O1,O2,Ok,执行时执行时间分别为间分别为t1, t2, , tk,每种运算的次数为每种运算的次数为e1, e2, , ek,则有则有u一般情况下一般情况下,不考虑每种运算的时间差异不考虑每种运算的时间差异()()1,ki iiT N It e N I=()()1,kiiT N Ie N I=辽辽宁宁师师范大范大学计学计算机算机与与信息技信息技术学术学院院 宋宋传鸣传鸣算法算法设计与
28、设计与分析分析概述概述有代表性的算法复杂性有代表性的算法复杂性课程介绍课程介绍什么是算法什么是算法算法的描述算法的描述算法分析算法分析评价规模为评价规模为N的某些或某类有代表性的合法输入的某些或某类有代表性的合法输入时的算法复杂度时的算法复杂度u最坏情况下的时间复杂度最坏情况下的时间复杂度u最好情况下的时间复杂度最好情况下的时间复杂度u平均情况下的时间复杂度平均情况下的时间复杂度pDN表示规模为的合法输入的集合表示规模为的合法输入的集合,P(I)表示出表示出现输入现输入I的概率的概率()()max,max,NIDTN IT N I=()()min,min,NIDTN IT N I=()( )
29、(),NavgIDTN IP I T N I=辽辽宁宁师师范大范大学计学计算机算机与与信息技信息技术学术学院院 宋宋传鸣传鸣算法算法设计与设计与分析分析概述概述例例: :插入排序和合并排序的复杂性分析插入排序和合并排序的复杂性分析课程介绍课程介绍什么是算法什么是算法算法的描述算法的描述算法分析算法分析插入排序插入排序(升序排列升序排列):每次选取未排序数中的第一每次选取未排序数中的第一个数个数,将其插入已排好序数列的合适位置将其插入已排好序数列的合适位置代价代价 执行次数执行次数 C1 n C2 n1 C3 n1 C4 sum(tj) C5 sum(tj1) C6 sum(tj1) C7 n1
30、InsertionSort(A) for j2 to length(A) keyAj ij-1 while i0 and Aikey Ai+1Ai ii-1 end while Ai+1key end for 辽辽宁宁师师范大范大学计学计算机算机与与信息技信息技术学术学院院 宋宋传鸣传鸣算法算法设计与设计与分析分析概述概述例例: :插入排序和合并排序的复杂性分析插入排序和合并排序的复杂性分析课程介绍课程介绍什么是算法什么是算法算法的描述算法的描述算法分析算法分析插入排序的时间复杂度插入排序的时间复杂度最好情况下最好情况下:输入数组已排好序输入数组已排好序,每次不进入每次不进入while循环循环
31、,则有则有最好情况下最好情况下:输入数组逆序输入数组逆序,Ai必须与已排好序的必须与已排好序的元素逐一比较元素逐一比较,因此因此tj=j,则有则有( )()()()()()()1234572221111611nnnjjjjjjT nC nCnCnCtCtCtCn=+-+-+-+-+-+-邋( )()()()()min123471111TnC nCnCnCnCnanb=+-+-+-+-+:( )()()()()()()max123425671111211122n nTnC nCnCnCn nn nCCCnanbnc轾+犏=+-+-+-犏臌-+-+:( )()22112nnjjjn ntj=+=-
32、邋()()()221112nnjjjn ntj=-=-=邋辽辽宁宁师师范大范大学计学计算机算机与与信息技信息技术学术学院院 宋宋传鸣传鸣算法算法设计与设计与分析分析概述概述例例: :插入排序和合并排序的复杂性分析插入排序和合并排序的复杂性分析课程介绍课程介绍什么是算法什么是算法算法的描述算法的描述算法分析算法分析插入排序的时间复杂度插入排序的时间复杂度平均情况下平均情况下:Ai必须与已排好序的一半元素逐一必须与已排好序的一半元素逐一比较比较,因此因此tj=j/2,则有则有( )()()()()()()1234572221111611nnnjjjjjjT nC nCnCnCtCtCtCn=+-+
33、-+-+-+-+-邋( )2avgTndnenf+:( )()2211242nnjjjn njt=+=-邋()222321124nnjjjjnnt=骣-+-=-=桫邋辽辽宁宁师师范大范大学计学计算机算机与与信息技信息技术学术学院院 宋宋传鸣传鸣算法算法设计与设计与分析分析概述概述例例: :插入排序和合并排序的复杂性分析插入排序和合并排序的复杂性分析课程介绍课程介绍什么是算法什么是算法算法的描述算法的描述算法分析算法分析合并排序合并排序:将待排序元素分成大小大致相同的两个将待排序元素分成大小大致相同的两个子集合子集合,然后分别将排好序的子集合合并成所要求然后分别将排好序的子集合合并成所要求的排好
34、序的集合的排好序的集合辽辽宁宁师师范大范大学计学计算机算机与与信息技信息技术学术学院院 宋宋传鸣传鸣算法算法设计与设计与分析分析概述概述例例: :插入排序和合并排序的复杂性分析插入排序和合并排序的复杂性分析课程介绍课程介绍什么是算法什么是算法算法的描述算法的描述算法分析算法分析合并排序合并排序:将待排序元素分成大小大致相同的两个将待排序元素分成大小大致相同的两个子集合子集合,然后分别将排好序的子集合合并成所要求然后分别将排好序的子集合合并成所要求的排好序的集合的排好序的集合假如假如n为为2的幂次的幂次,递归算法要递归递归算法要递归(log2n+1)层层,每每一层需要计算一层需要计算cn次次,因
35、此因此( )( )( )minmax2logavgTnTnTncnncn=+输入输入:n个元素的数组个元素的数组A1.n输出输出:按非降序排列的数组按非降序排列的数组A1.nMergeSort(A,left,right) if leftN时时,有有an2+bn+cdnlog2n+dn,即即:合并排序的时间复杂性低于插入排序合并排序的时间复杂性低于插入排序实例实例u计算机计算机A每秒执行每秒执行10亿条指令亿条指令,计算机计算机B每秒执行每秒执行1千万条指令千万条指令.由由A执行插入排序执行插入排序,B执行合并排序执行合并排序u插入排序的插入排序的T(n)简化为简化为c1n2,合并排序的合并排序
36、的T(n)简化为简化为 c2nlog2n,并设并设c1=2,c2=50u要排序要排序100万个数万个数,A机器需要机器需要2000秒秒,B机器大约需机器大约需要要100秒秒u要要排序排序1000万个数万个数,A机器需要机器需要2.3天天,B机器需要机器需要20分钟分钟u随着问题规模的增长随着问题规模的增长,合并排序的相对优势更明显合并排序的相对优势更明显辽辽宁宁师师范大范大学计学计算机算机与与信息技信息技术学术学院院 宋宋传鸣传鸣算法算法设计与设计与分析分析概述概述例例: :插入排序和合并排序的复杂性分析插入排序和合并排序的复杂性分析课程介绍课程介绍什么是算法什么是算法算法的描述算法的描述算法
37、分析算法分析一般考察算法的最坏情况下的运行时间一般考察算法的最坏情况下的运行时间uTmax(n)是算法再任何输入下的运行时间上界是算法再任何输入下的运行时间上界u对于某些算法对于某些算法,最坏情况出现得相当频繁最坏情况出现得相当频繁p如在数据库中检索根本不存在的信息如在数据库中检索根本不存在的信息u大致看来大致看来, Tavg(n)通常与通常与Tmax(n)一样差一样差辽辽宁宁师师范大范大学计学计算机算机与与信息技信息技术学术学院院 宋宋传鸣传鸣算法算法设计与设计与分析分析概述概述知名学者知名学者课程介绍课程介绍什么是算法什么是算法算法的描述算法的描述算法分析算法分析姚期智姚期智姚期智姚期智(
38、Andrew Chi-(Andrew Chi-ChihChih Yao), Yao),世界著名计算机学世界著名计算机学家家,2000,2000年图灵奖得主年图灵奖得主, ,美国科学院院士美国科学院院士, ,美国科学美国科学与艺术学院院士与艺术学院院士, ,中国科学院外籍院士中国科学院外籍院士, ,清华大学高清华大学高等研究中心教授等研究中心教授.1967.1967年获得台湾大学物理学士学年获得台湾大学物理学士学位位,1972,1972年获得美国哈佛大学物理博士学位年获得美国哈佛大学物理博士学位,1975,1975年年获得美国伊利诺依大学计算机科学博士学位获得美国伊利诺依大学计算机科学博士学位.
39、1975.1975年至年至19861986年曾先后在美国麻省理工学院数学系、年曾先后在美国麻省理工学院数学系、斯坦福大学计算机系、加利福尼亚大学伯克利分校斯坦福大学计算机系、加利福尼亚大学伯克利分校计算机系任助教授、教授计算机系任助教授、教授.1986.1986年至年至20042004年在普林年在普林斯顿大学计算机科学系担任斯顿大学计算机科学系担任WiliamWiliam and Edna and Edna MacaMacaleerleer工程与应用科学教授工程与应用科学教授.2004.2004年起在清华大学任年起在清华大学任全职教授全职教授. .多年来多年来, ,姚期智先生以其敏锐的科学思维
40、姚期智先生以其敏锐的科学思维, ,不断向新的学术领域发起不断向新的学术领域发起冲击冲击, ,在数据组织、基于复杂性、姚期智的伪随机数生成理论、密在数据组织、基于复杂性、姚期智的伪随机数生成理论、密码学、通信复杂性乃至量子通信和计算等多个尖端科研领域，都码学、通信复杂性乃至量子通信和计算等多个尖端科研领域，都做出了巨大而独到的贡献做出了巨大而独到的贡献. .他所发表的近百篇学术论文他所发表的近百篇学术论文, ,几乎覆盖了几乎覆盖了计算复杂性的所有方面计算复杂性的所有方面, ,并在获图灵奖之前并在获图灵奖之前, ,就已经在不同的科研领就已经在不同的科研领域屡获殊荣域屡获殊荣, ,曾获美国工业与应用
41、数学学会乔治曾获美国工业与应用数学学会乔治波利亚奖和以算法波利亚奖和以算法设计大师克努特命名的首届克努特奖设计大师克努特命名的首届克努特奖, ,是计算机理论方面国际上最是计算机理论方面国际上最拔尖的学者拔尖的学者. .辽辽宁宁师师范大范大学计学计算机算机与与信息技信息技术学术学院院 宋宋传鸣传鸣算法算法设计与设计与分析分析概述概述知名学者知名学者课程介绍课程介绍什么是算法什么是算法算法的描述算法的描述算法分析算法分析陈国良陈国良陈国良任中国科学技术大学教授陈国良任中国科学技术大学教授, ,博士生导师博士生导师, ,现任中国科学技术大学软件学院院长现任中国科学技术大学软件学院院长, ,国家高国家
42、高性能计算中心（合肥）主任性能计算中心（合肥）主任, ,智能感知与图像智能感知与图像理解教育部重点实验室（西安电子科技大学）理解教育部重点实验室（西安电子科技大学）学术委员会主任学术委员会主任. .中国计算机学会高性能计算中国计算机学会高性能计算专业委员会主任专业委员会主任, ,享受国家政府特殊津贴享受国家政府特殊津贴.197.1973 3年起在中国科学技术大学任教年起在中国科学技术大学任教. .陈国良陈国良20032003年当选中国科学院院士年当选中国科学院院士, ,国家教育部高等学校国家教育部高等学校计算机科学技术教学指导委员会副主任计算机科学技术教学指导委员会副主任, ,全国全国首届高等
43、学校教学名师首届高等学校教学名师, ,安徽省计算机学会理安徽省计算机学会理事长事长, ,国际高性能计算（亚洲）常务理事国际高性能计算（亚洲）常务理事. .他是我国非数值并行算法研究的学科带头人他是我国非数值并行算法研究的学科带头人, ,他围绕着并行算法的他围绕着并行算法的教学与研究教学与研究, ,逐渐形成了逐渐形成了“算法理论算法设计算法实现算法算法理论算法设计算法实现算法应用应用”一套完整的并行算法学科体系一套完整的并行算法学科体系, ,提出了提出了“结构算法编程结构算法编程”一体化的并行计算研究方法一体化的并行计算研究方法. .他率先创建的我国第一个国家高性能他率先创建的我国第一个国家高性
44、能计算中心是我国并行算法研究、环境科学与工程计算软件等的科计算中心是我国并行算法研究、环境科学与工程计算软件等的科研与教学基地研与教学基地, ,在学术界和教育界有一定的影响和地位在学术界和教育界有一定的影响和地位. . 辽辽宁宁师师范大范大学计学计算机算机与与信息技信息技术学术学院院 宋宋传鸣传鸣算法算法设计与设计与分析分析概述概述知名学者知名学者课程介绍课程介绍什么是算法什么是算法算法的描述算法的描述算法分析算法分析徐家福徐家福19481948年毕业于中央大学数学系年毕业于中央大学数学系.1957.1957年至年至19591959年在前苏联莫斯科大学进年在前苏联莫斯科大学进修修. .历任南京
45、大学副教授、教授、计历任南京大学副教授、教授、计算机软件研究所所长算机软件研究所所长, ,国务院学位委国务院学位委员会第一、二届学科评议组成员员会第一、二届学科评议组成员, ,中中国计算机学会第一届副理事长、软国计算机学会第一届副理事长、软件专业委员会主任委员件专业委员会主任委员, ,江苏省计算江苏省计算机学会第一、二、三届理事长机学会第一、二、三届理事长. .徐家福一直致力于软件自动化研究徐家福一直致力于软件自动化研究, ,成为我国计算机软件的奠基人成为我国计算机软件的奠基人之一之一. .他曾主持并参与研制成他曾主持并参与研制成1414个软件系统个软件系统, ,研究成果被广泛应用于研究成果被
46、广泛应用于国防建设与国计民生中的各种计算问题国防建设与国计民生中的各种计算问题. . 研制出我国第一个研制出我国第一个ALGOLALGOL系统、系统程序设计语言系统、系统程序设计语言XCYXCY、多、多种规约语言种规约语言; ;参加制定参加制定ALGOLALGOL，COBOLCOBOL国家标准国家标准; ;率先在我国研制率先在我国研制出数据驱动计算机模型出数据驱动计算机模型FPMND;FPMND;研制出兼顾函数式和逻辑式风格研制出兼顾函数式和逻辑式风格的核心语言的核心语言KLNDKLND及相应的并行推理系统及相应的并行推理系统; ;完成完成8 8个软件自动化系统个软件自动化系统, ,如基于自行
47、设计规约语言如基于自行设计规约语言GSPECGSPEC的的NDAUTONDAUTO系统系统, ,基于基于FGSPECFGSPEC的的算法设计自动化系统算法设计自动化系统NDADASNDADAS和自学习软件自化系统和自学习软件自化系统NDSAILNDSAIL等等辽辽宁宁师师范大范大学计学计算机算机与与信息技信息技术学术学院院 宋宋传鸣传鸣算法算法设计与设计与分析分析概述概述知名研究机构知名研究机构课程介绍课程介绍什么是算法什么是算法算法的描述算法的描述算法分析算法分析中科院软件所计算机科学国家重点实验室中科院软件所计算机科学国家重点实验室u从事计算机科学、信息安全等从事计算机科学、信息安全等北京
48、大学软件研究所北京大学软件研究所u软件工程、软件工程、OS与中间件、计算机科学理论、信息与中间件、计算机科学理论、信息安全等安全等南京大学软件新技术国家重点实验室南京大学软件新技术国家重点实验室u软件自动化、分布计算与并行处理、软件方法学软件自动化、分布计算与并行处理、软件方法学等等中国科技大学计算机科学与技术学院中国科技大学计算机科学与技术学院u高性能计算等高性能计算等上海交通大学计算机科学与技术系上海交通大学计算机科学与技术系复旦大学计算机科学与技术系复旦大学计算机科学与技术系大连理工大学理论计算机科学研究所大连理工大学理论计算机科学研究所辽辽宁宁师师范大范大学计学计算机算机与与信息技信息技术学术学院院 宋宋传鸣传鸣算法算法设计与设计与分析分析概述概述做研究的三个境界与大家共勉做研究的三个境界与大家共勉课程介绍课程介绍什么是算法什么是算法算法的描述算法的描述算法分析算法分析昨夜西风凋碧树昨夜西风凋碧树,独上高楼独上高楼,望断天涯路望断天涯路衣带渐宽终不悔衣带渐宽终不悔,为伊消得人憔悴为伊消得人憔悴众里寻她千百度众里寻她千百度,蓦然回首蓦然回首,那人却在灯火阑珊处那人却在灯火阑珊处王国维人间词话辽辽宁宁师师范大范大学计学计算机算机与与信息技信息技术学术学院院 宋宋传鸣传鸣算法算法设计与设计与分析分析概述概述
