算法第1章算法概述详解.ppt

1 计算机算法设计与分析 主讲人 袁运浩E mail yhyuan 计算机科学与技术系江南大学物联网工程学院 2 课时数 48节上课 1 16周成绩 卷面成绩 70 平时成绩 30 教材 计算机算法设计与分析 王晓东 电子工业出版社 2012参考书 1 算法设计与分析 郑宗汉 郑晓明 清华大学出版社 2 算法导论 ThomasH Cormen编著 潘金贵等译 机械工业出版社 3 3 主要内容介绍 第1章算法概述第2章递归与分治策略第3章动态规划第4章贪心算法第5章回溯法第6章分支限界法 4 4 意念与现实 1 一个例子 给你一个无限容积的罐子和无限个球 球从1开始连续编号 在差1分钟到零点时 将标号为1 10的10个球放进罐子 然后将10号球从罐子里拿出 在差1 2分钟到零点时 将标号为11 20的10个球放进罐子 然后将20号球从罐子里拿出 在差1 4分钟到零点时 将标号为21 30的10个球放进罐子 然后将30号球从罐子里拿出 就这样将游戏进行下去 假定放球和取球不占时间 请问 当时钟指向零点时 罐子里还剩多少个球 5 5 意念与现实 2 一个例子 这个答案很直接 无穷多个球 所有编号不是10n n 1 的球在放进罐子里后就不会再拿出来 而在到达零点之前这种放球 取球的次数是无限的 因此 罐子里面的球在零点时将是无数个 你很确信这个答案吗 现在来让我们改变拿球的方式 将每次拿10 20 30 号球分别变为拿1 2 3 号球 即第x次拿球 所拿出来的球的编号是x 结果又会怎样呢 这个时候 神奇的事情发生了 这个罐子里面的球数将为0 对于任意一个球 设其编号为n 则在差 1 2 n 1分钟到零点时该球将被取出 也就是说 对于任意球n 在零点时它都不在罐子里 因此 零点时罐子里球的个数为0 6 6 意念与现实 3 一个例子 对于有些人来说 这个答案似乎不可接受 但又确实找不到驳斥的办法 你能找出来吗 也许这个答案是合理的 因为拿球顺序的变化使得算法发生了变化 即我们实际上讨论的是两个算法 可仔细一想又觉得不对 因为两个算法都是每次放进10个球 拿出1个球 即从根本上说 这是两个一样的算法 怎么会有截然相反的结果呢 7 7 意念与现实 4 一个例子 如果我们再次改变试验中拿球的方式 将拿某个特定标号的球改为取出任意标号的球 即在差1分钟到零点时 将标号为1 10的10个球放进罐子 然后从罐子里任意拿出一个球 在差1 2分钟到零点时 将标号为11 20的10个球放进罐子 然后从罐子里任意拿出一个球 在差1 4分钟到零点时 将标号为21 30的10个球放进罐子 然后从罐子里任意拿出一个球 这种拿球方式又将产生何种结果呢 答案是仍然是0太不可思议了吧 这三个本质相同的算法怎么有如此匪夷所思的结果呢 如果非要说这三个算法有什么不同 就是拿球时的标号不同 但难道标号的不同使最后球的数量发生了变化 8 8 意念与现实 5 一个例子 没错 就是这个标号对结果产生了深远影响 从某种意义上说 标号是虚的 它只存在于我们的想象中 但确实对现实结果产生了影响 即我们的思维使算法发生了变化 或许从另一个角度来看 这个问题就是 没有就是无穷 无穷就是没有 它们之间也许根本没有什么不同 它们的不同只存在于人们的想象或者意念中 也许这是为什么无穷的符号是由两个0连接而成的 从左右两面看都是无有 而从中间看则是无穷 从这个意义上说 算法是一种思维方式 AlgorithmicThinking 或者说一种哲学 9 一个最简单的算法 1 起床2 吃早点3 上早自习4 上课5 吃午饭6 上课7 吃晚饭8 上晚自习9 睡觉 10 11 11 12 12 13 13 1 1 2算法及其重要性质 算法 是指解决问题的一种方法或一个过程 算法是由若干条指令组成的有穷序列 满足性质 1 输入 有0个或多个由外部提供的量作为算法的输入 2 输出 算法产生至少一个量作为输出 1个或多个 3 确定性 组成算法的每条指令是清晰 无歧义的 4 有限性 算法中每条指令的执行次数是有限的 执行每条指令的时间也是有限的 14 14 算法与程序的区别 程序是算法用某种程序设计语言的具体实现 程序可以不满足算法的性质 4 例如 操作系统是一个在无限循环中执行的程序 因而不是一个算法 操作系统的各种任务可看成是单独的问题 每一个问题由操作系统中的一个子程序通过特定的算法来实现 该子程序得到输出结果后便终止 15 15 1 1 3算法的描述方法 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 1 2算法复杂性分析 26 26 算法复杂性 算法复杂性的高低体现在运行该算法所需要的计算机资源的多少上 所需资源越多 算法复杂性越高 反之 所需资源越少 算法复杂性越低 算法的复杂性有 时间复杂性与空间复杂性时间复杂性 算法运行所需要的时间资源量空间复杂性 算法运行所需要的空间资源量选用算法应遵循的一个重要原则 当给定的问题有多种算法时 选择其中复杂性最低者 27 27 算法复杂性 1 时间 空间资源的量只依赖于算法要解的问题的规模 算法的输入和算法本身的函数 分别用N I和A表示算法要解问题的规模 算法的输入和算法本身 而且用C表示复杂性 那么 应该有C F N I A 一般把时间复杂性和空间复杂性分开 并分别用T和S来表示 则有 T T N I 和S S N I 通常 让A隐含在复杂性函数名当中 28 28 算法复杂性 2 设一台计算机所提供的元运算有k种 分别记为O1 O2 Ok同时 设每执行一次这些元运算所需要时间分别为t1 t2 tk对于给定的算法A 设用到元运算Oi的次数为ei ei N I 那么 显然 对于不同的N和I T N I 有多种可能的值 对于给定问题规模 算法A的时间复杂性到底是多少 29 29 1 2 1最好 最坏与平均情况 最坏情况下的时间复杂性 最好情况下的时间复杂性 平均情况下的时间复杂性 其中DN是规模为N的合法输入的集合 I 是DN中使T N I 达到Tmax N 的合法输入 实践表明 可操作性最好且最有实际价值的时间复杂性 是DN中使T N 达到Tmin N 的合法输入 而P I 是在算法的应用中出现输入I的概率 30 30 31 31 32 32 33 算法渐近复杂性 设T N 是算法A的复杂性函数 一般满足 当N T N 即对于T N 若存在t N 使得当N T N t N T N 0 那么就说t N 是T N 的渐近性态 或称为算法A的渐近复杂性 在数学上 t N 是T N 的渐近表达式 是T N 略去低阶项留下的主项 例如 t N 比T N 简单 34 34 1 2 2渐近符号 例如 1 由于对所有的N 1有3N 4N 则3N O N 2 由于对所有的N 1有N 1024 1025N 则N 1024 O N 3 由于对所有的N 1有N2 N3 则N2 O N3 4 由于对所有的N 10有2N2 11N 10 3N2 则2N2 11N 10 O N2 35 35 1 2 2渐近符号 根据O的定义 容易证明它有如下运算规则 1 O f O g O max f g 2 O f O g O f g 3 O f O g O fg 4 如果g N O f N 则O f O g O f 5 O Cf N O f N 其中C是一个正的常数 6 f O f 36 36 1 2 2渐近符号 的定义 如果存在正的常数C和自然数N0 使得当N N0时有f N Cg N 则称函数f N 当N充分大时下有界 且g N 是它的一个下界 记为f N g N 即f N 的阶不低于g N 的阶 的定义 定义f N g N 当且仅当f N O g N 且f N g N 此时称f N 与g N