算法分析第一章讲解.ppt

介绍： 张公敬 Mail：zhang8887327@163.com 办公室：博知楼 信息安全系办公室 Phone同学自我介绍： 你的姓名? 你的导师？ 毕业学校？ 本科阶段学习过《算法分析》课程？ 学习过数据结构？C语言？c++？ 教材及参考 教材：计算机算法设计与分析（ISBN 7-121-00001-6） 王晓东 电子工业出版社 25.5元 2005.12出版 参考： 算法设计与分析（ISBN 7-302-10894-3 ）郑宗汉 郑晓明 清华大学出版社 2004.11 32元 ALGORITHM DESIGN （算法设计）英文版 Jon Kleinberg / Eva Tardos著 68元 清华大学出版社，( ISBN 7-302-12260-1) 学习及考核 学习方式：授课、课堂讨论与演讲 考核方式： 平常成绩：20% { 课堂讨论20， 作业30 出勤30， 演讲 20 } 期末考试：80% 解释： 作业： 每章结束后布置作业，每章每人1-2题。　一周内提交作业，要求独立完成，不得抄袭。提交含电子文档、代码及运行程序。，缺一次　平时成绩－５分。 演讲 题目：选取每章有代表性并有一定难度练习题、或算法研究方面的文章，关于算法的设计、分析、改进、实现等的介绍。 要求：一人一题，难度适中、表达清楚、准确. 时长：20分钟 考核内容：（电子文档）文本内容正确、组织合理，表达清楚、准确。　　　　　　　　 时间：安排自第4周－17周，提前报演讲题目， 人数：每周按排3人。按点名册顺序。 作业布置及提交 Zhang8887327@163.com 提交时作业时文件名写： “２０13研姓名（第X章）” 课后用个人邮箱发送邮件给我。主题写2013研究生（xxx）即可。 第1章 算法概述 学习要点: 理解算法的概念。 理解什么是程序，程序与算法的区别和内在联系。 掌握算法的计算复杂性概念。 掌握算法渐近复杂性的数学表述。 解递归方程（将在本章结束后讲解） 掌握用C++语言描述算法的方法。 1.1算法与程序 算法+数据结构=程序 =〉 算法是程序的灵魂。 程序设计:行为设计+结构设计 行为设计:对要解决的问题，提出达到目的需要实施的一些步骤，并对这些步骤加以必要的细化，给予定义，在此基础上用某种方式完整地描述出来，就是行为设计，其结果就是算法； 结构设计是针对所要解决的问题，对数据定义数据结构（包括物理结构和逻辑结构）。 程序：有了好的算法、合适的数据结构，再使用某种程序设计语言加以具体实现，即可得到程序 算法是一个有穷规则（指令）的集合。它为某个特定类型问题提供了解决问题的运算序列。（非形式化定义） 算法(Algorithm) 算法是指解决问题的一种方法或一个过程。 算法是若干指令的有穷序列，满足性质： (1)输入：有外部提供的量作为算法的输入。 (2)输出：算法产生至少一个量作为输出。 (3)确定性：组成算法的每条指令是清晰，无歧义的。 (4)有限性：有限条指令，有限时间执行。 综上所述，所谓算法是一组定义严谨的运算顺序规则 程序(Program) 程序是算法用某种程序设计语言的具体实现。 程序可以不满足算法的性质(4)。 例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。 操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。 问题求解(Problem Solving) 算法复杂性分析 算法复杂性 = 算法所需要的计算机资源 算法的时间复杂性T(n)； 算法的空间复杂性S(n)。 其中n是问题的规模（输入大小）。 算法的时间复杂性 （1）最坏情况下的时间复杂性 Tmax(n) = max{ T(I) | size(I)=n } （2）最好情况下的时间复杂性 Tmin(n) = min{ T(I) | size(I)=n } （3）平均情况下的时间复杂性 Tavg(n) = 其中I是问题的规模为n的实例，p(I)是实 例I出现的概率。 算法渐近复杂性 T(n) ?? , as n?? ; (T(n) - t(n) )/ T(n) ?0 ，as n??; t(n)是T(n)的渐近性态，为算法的渐近复杂性。 在数学上， t(n)是T(n)的渐近表达式，是T(n)略去低阶项留下的主项。它比T(n) 简单。 渐近分析的记号 在下面的讨论中，对所有n，f(n) ? 0，g(n) ? 0。 （1）渐近上界记号O (omicron)