第1单元 算法及基础知识.pptVIP

算法分析 张阳 信息工程学院 教师简介 张阳 信息工程学院109 zhangyang@nwsuaf.edu.cn 教学资源：作业管理系统-张阳 课程简介 课时：理论课36+实验课12=48 成绩：平时30+考试70=100 平时：作业+实验+实验考核+考勤 教材： 《算法设计与分析》王秋芬、吕聪颖等编著 清华大学出版社 2011年8月 参考 算法设计与分析 王晓东 第二版 清华大学出版社 （JAVA） 算法设计与分析 王晓东 第二版 清华大学出版社（C/C++） 课程简介 学习算法的理由： 一个人接受科技教育得到的最大收获，是那些能够受用一生的一般性智能工具。 ——George Forsythe 《计算机科学家到来以前我们做什么》1968 算法是计算机科学的基石。没有算法，计算机程序将不复存在，另外学习算法可以提高人们的分析能力。 算法可以看作是解决问题的一类特殊方法——它虽非问题的答案，但它是经过准确定义的，用来获得答案的过程。 无论是否涉及计算机，特定的算法设计技术都能看作是问题求解的有效策略。 课程简介 算法的魅力：思考 程序=算法+数据结构 算法让我们上一个更高的台阶 要求: 思考+预习/复习+实践 上课：不旷课、不迟到 课程简介 第1章 算法及基础知识 第2章 贪心法 第3章 分治法 第4章 动态规划 第5章 有哪些信誉好的足球投注网站法 第6章 随机化算法 第9章 NP完全理论 第1章 算法概述 学习要点: 理解算法的概念。 理解什么是程序，程序与算法的区别和内在联系。 掌握算法的计算复杂性概念。 掌握用C++/JAVA语言描述算法的方法。 第1章 算法概述 算法： 对于计算机科学来说，算法指的是对特定问题求解步骤的一种描述，是若干条指令的有穷序列。 算法的特性 输入（0个或多个）、输出（至少1个）、确定性（无歧义）、有限性、可行性 描述方式 自然语言、图形、程序设计语言、伪代码 本书采用了面向对象程序设计语言C++ 思考：算法与程序的区别？ 第1章 算法概述 程序(Program) 程序是算法用某种程序设计语言的具体实现。 程序可以不满足算法的性质(4)。 操作系统：是一个在无限循环中执行的程序，因而不是一个算法。 操作系统的各种任务：可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。 最大共约数 求：非负整数M和N的最大公约数， 记为：Gcd(m,n) 方法一：欧几里得算法 Gcd(m,n)=Gcd(n, m mod n) Gcd(60,24)=Gcd(24,12)=Gcd(12,0)=12 方法二：连续整数检测算法 （1）将 min(m,n) 的值赋给t。 （2）m除以t，如果余数为0，进入第3步，否则，进入第4步。 （3）n除以t，如果余数为0，返回t值，结束，否则，进入第4步。 （4）t=t-1 ，返回第2步。 方法三：中学里计算Gcd(m,n)的过程（用数学定义的方法） （1）找到m的所有质因数。 （2）找到n的所有质因数。 （3）找到（1），（2）中的公因数。 （4）求公因数的积，该乘积为m、n的最大公约数。 问题求解(Problem Solving) 算法设计 1．理解问题 2．了解计算机设备的性能 3．在精确解法和近似解法间做选择 4．确定适当的数据结构 5．算法设计技术 6．详细表述算法的方法 7．证明算法的正确性 8．分析算法 9．为算法写代码 问题 N后问题 01背包问题 布线问题 01背包问题 布线问题 1.3 算法分析 算法复杂性 = 算法运行时所需要的计算机资源的量 时间复杂性、空间复杂性 影响时间复杂性的因素 问题规模n、输入序列I、算法本身A 影响空间复杂性的因素 算法本身、输入输出数据、辅助变量 算法复杂性的权衡 时间复杂度和空间复杂度相互影响 时间换空间或空间换时间 1.3 算法分析 例：查找操作，三种情况下的复杂性 最好情况Tmin（N) 1次 最坏情况Tmax（N) N次 平均情况Tavg（N) (N+1)/2 1.3 算法分析 算法渐近复杂性态 设算法的运行时间为T(n)，如果存在T*(n)，使得 就称T*(n)为算法的渐进性态或渐进时间复杂性。 1.3 算法分析 假设算法A的运行时间表达式为T1(n) T1(n)=30n4+20n3+40n2+46n+100 假设算法B的运行时间表达式为T2(n) T2(n)=1000n3+50n2+78n+10