算法概述概要PPT学习教案

1、会计学1 算法概述概要算法概述概要 第1页/共36页 电子计算机的出现是本世纪的一件大事，因为它 改变了我们这个世界的面貌。可以毫不夸张地这么 说，今天人们依赖于计算机，就象人们依赖于电力 ，如果它暂停了，社会就无法运转。 快速电子计算机贵在神速，也就是它的运算速度 快，同时它的发展之迅速也是惊人的。从每秒5000 次运算，发展到现在的运算速度每秒数千亿次运算 。元器件从继电器、真空管、晶体管、集成电路、 大规模集成电路，发展到超大规模集成电路。结构 上从每台机器作为运算工具的“单兵作战”模式， 发展到今天将范围遍及各大洲的计算机网络，算法 也从单机的串行计算发展到网络上并行的分布计算 。 第

2、2页/共36页 一台作109次/秒运算（1G）的计算机的效率超过 10亿人同时工作。它可以作中期的天气预报，可以 控制庞大的化工厂生产过程，以至于还可以驾驭现 代化战争，从这个意义上来说它确实是近乎神奇的 。不过必须强调的是这些都是在人的安排下进行工 作的。比如人们利用计算机作天气预报，必须依据 天气变化规律，作出它的偏微分方程数学模型，以 及编好程序，指导计算机按照人的安排一步步地工 作，计算预报数据，绘制气象云图。 这就是说，计算机虽然神通广大，还是在人的 控制下工作。同时还应说明计算机并非什么都能做 ，有的事情理论上它根本做不了。讨论哪些事计算 机能做，哪些事计算机做不了，属于可计算性理

3、论 研究的范畴。还有一些问题理论上计算机虽是能做 ，但实际上又是不可能完成的。 第3页/共36页 比如拿最简单例子，26个英文字母全排列，它的 排列数为： 26！41026 以每年365天计算，共有 3652436003.1536107秒 以每秒能完成107个排列的超高速电子计算机来做这 项工作，需要 41026/(3.15361014)1.21012年 即使计算机运行速度随着技术的提高，恐怕也还是 不可能实现的。因计算机的速度再提高也有它的极 限。 第4页/共36页 任何一项计算，总要事先拟定计算方案和规划计算 步骤。为使计算机的计算过程能够解决某一问题，必须 为计算机设计执行的解决方案中的

4、每个详细步骤，并且 将此过程完整地描述出来。所谓算法是对某个问题求解 方案的完整而明确的描述。 与算法有关的还有一个大家熟悉的公式： 程序程序= =算法十数据结构算法十数据结构 也就是说，算法设计和程序设计是不完全相同的。 由于数字计算机运算速度很高，是人工手算所不能比拟 的。为了充分发挥计算机的这种优点，在用计算机求解 问题过程中，应尽量减少人工干预。因此，必须先将所 制定的解决方案“告诉”计算机，使计算机按照人们规 定的计算顺序去自动执行。用计算机能接受的“语言” 来描述解题步骤，这项工作叫做程序设计，它还包含了 需要使用合适的数据结构。 第5页/共36页 “算法设计与分析”是研究算法的一

5、门学科。它 还很年轻远未定型，还处在发展中。有人说“计算 机科学是一门研究算法的科学”。不论这个说法是 否全面，算法无疑是计算机科学的重要组成部分。 它近来发展极其迅速。“算法设计与分析”已是计 算机专业本科生的一门必需掌握的内容。 1.1.一些有趣的问题一些有趣的问题 (1) 巡回推销员问题巡回推销员问题:设有n个城市，已知任意两城 市间之距离，现有一推销员想从某一城市出发巡回 经过每一城市（且每城市只经过一次），最后又回 到出发点，问如何找一条最短路径。 第6页/共36页 设距离矩阵如下： 018657264 180567355 65560417 727341039 64557390 D

6、试一试求出最短路径。 第7页/共36页 （2)2) 皇后问题皇后问题:这是高斯1850年提出的一个著名问题 ： 国际象棋中的“皇后”在横向、直向、和斜向都 能走步和吃子，问在nn 格的棋盘上如何能摆上n个 皇后而使她们都不能互相吃。 当n很大时，问题很难。 对于n=8,现已知此问题共有92种解，但只有12种 是独立的，其余的都可以由这12种利用对称性或旋转 而得到。 设n=4，试一试。 第8页/共36页 (3 (3）设天平有一些25克的砝码，一些10克的砝码 ，一些5克的砝码和一些1克的砝码。现要称63克的 物体，问至少需要用几个砝码。 (4(4）背包问题背包问题1 1：有一旅行者要从n种物品

7、中选取 不超过b公斤重的行李随身携带，要求总价值最大 。 例：设背包的容量为50千克。物品1重10千克，价 值60元；物品2重20千克，价值100元；物品3重30 千克，价值120元。求总价值最大。 （5 5）背包问题背包问题2 2：设有n=8个体积分别为54，45， 43，29，23，21，14，1的物体和一个容积为C=110 的背包，问选择哪几个物体装入背包可以使其装的 最满。 第9页/共36页 （6 6）装箱问题：装箱问题：设有体积分别为v1,v2,vn的n种物 品u1,u2,un装到容量为L的箱子里。不同的装箱方案 所需的箱子数目可能不同，问如何装箱能装完这n种 物品且使用的箱子数目最

8、少。 （7 7）平面图的四色猜想问题：平面图的四色猜想问题：一个平面图是否用四 种颜色就可使相邻的区域颜色都不相同？ 第10页/共36页 2 2研究算法的重要性研究算法的重要性 假设某一负责人交给你一个很难的任务，几天后询问 你问题解决了没有。可能会发生如下图这样的情况： 问：“交给你的问题，解决方案设计出来了吗？” 答：“我找不到一个有效的算法来解决它，没能完成 任 务。” 第11页/共36页 问：“交给你的问题，解决方案设计出来了吗？ ” 答： “我找不到一个有效的算法来解决它，因 为 这样的算法是不存在的。” (不过，要证明一个问题不存在有效算法，往往 跟寻找有效算法一样难。)第12页/

9、共36页 问：“交给你的问题，解决方案设计出来了吗？” 答： “我找不到一个有效的算法来解决它，但不 是 我不行，因为所有这些名人也都找不到解决它 的有效算法。” 如果是你的话，你愿意是哪种结果？ 第13页/共36页 3. 3. 问题解决的好吗？问题解决的好吗？ 设计出解决问题的算法后，要知道算法的优劣好 坏，是好算法则不必对其怀疑而再浪费时间进行研究 。不是好算法则应再进行研究改进。而如何知道算法 的优劣好坏，需要学习分析算法的方法。 要设计出好算法，需要学习算法设计的常用方法 。 第14页/共36页 第15页/共36页 第16页/共36页 理解问题 精确解或近似解 选择数据结构 算法设计策

10、略 设计算法 第17页/共36页 第18页/共36页 第19页/共36页 第20页/共36页 第21页/共36页 第22页/共36页 评定算法优劣的标准要看它的时间复杂性、空间复 杂性和人工复杂性，其中时间复杂性最为重要，通常是 用它来衡量某个算法的“好”或“坏”。 不同的算法具有很不相同的时间复杂性函数，说它 们当中哪些“效率足够高”哪里“效率太低”，总要看 当时的情况。但是，计算机科学家们公认一种简单的区 别，这种区别对这些问题提供了重要的透彻的分析，这 就是多项式时间算法和非多项式时间算法之间的区别。 时间复杂性则表成n的函数T(n)。下表表示各种 T(n)的 算法在不同的n值时的运算时

11、间。 第23页/共36页 T(n)微 秒lognnnlognn 2 n 3 n 5 2 n 3 n n! n=103.310331001 毫 秒 0.1 秒 1 毫 秒 59 毫 秒 3.6 秒 n=405.340213160064 毫 秒 1.7 分 12.7 天 3855 世 纪 10 3 世 纪 n=605.9603543600216 毫 秒 1.3 分 366 世 纪 1.3 10 13 世 纪 10 66 世 纪 不同时间复杂性函数的对比 第24页/共36页 可以看出，不同T(n)的算法当n增长时运算 时间增长的快慢很不同。T(n)为指数形式的算 法当n较大时实际上是无法应用的。有些

12、算法 T(n)与n！成正比，它随n的加大比指数函数增 长还要快，这种算法更是没有实用价值。凡是 T(n)为n的对数函数、线性函数或多项式的(幂 函数也是多项式的特例)，我们称这类算法为“ 有效算法”，或好的算法；反之，凡是T(n)为 指数函数或阶乘函数的，称之为坏的算法。 第25页/共36页 提高计算速度对不同时间复杂性函数的影响对比 时间复杂性函数用现在的计算机用快 100 倍的计算机用快 1000 倍的计算机 nN1100N11000N1 n2N210N23.16N2 n3N34.64N310N3 n5N42.5N43.98N4 2nN5N5+6.64N5+9.97 3nN6N6+4.19

13、N6+6.29 第26页/共36页 为了分析方便，复杂性通常用数量级的形式表示 。如T(n)=O(f(n)，表示存在某一常数C，使得对所有 n1，都有T(n)Cf(n)。对于足够大的n，这样表示 很方便。 例：若T(n)=5n3+3n+12，则T(n)=O(n3)。 证：5n3+3n+125n3+3 n3+12 n3=20n3，对所有 n1成立，取C=20，则有T(n)Cn3 对于足够大的n，存在以下顺序： O(logn)O(n)O(nlogn)O(n2)O(n3) O(2n)O(3n)O(n!)。 第27页/共36页 算法复杂性是算法运行所需要的计算机资源的量 ， 需要时间资源的量称为时间复

14、杂性时间复杂性，需要的空间资源 的 量称为空间复杂性空间复杂性。这个量应该只依赖于算法要解的 问 题的规模、算法的输入和算法本身的函数。如果分别 用 N、I和A表示算法要解问题的规模、算法的输入和算法 本身，而且用C表示复杂性，那么，应该有C=F(N,I,A) 。 一般把时间复杂性和空间复杂性分开，并分别用T和S 来 表示，则有： T=T(N,I)和S=S(N,I) 。 （通常，让A隐含在复杂性函数名当中 ） 第28页/共36页 最坏情况下的时间复杂性 ： ),(max max INT(N)T N DI ),(max 1 INet k i ii DI N ),( * 1 INet k i ii

15、 ),( * INT 最好情况下的时间复杂性 ： ),(min min INT(N)T N DI ),(min 1 INet k i ii DI N ) ,( 1 INet k i ii ) ,(INT 平均情况下的时间复杂性 ： N DI INTIP(N)T),()( avg N DI k i ii INetIP),()( 1 其中DN是规模为N的合法输入的集合；I*是DN中使T(N, I*) 达到Tmax(N)的合法输入； 是中使T(N, )达到Tmin(N)的合法 输入；而P(I)是在算法的应用中出现输入I的概率。 I I 算法渐近复杂性算法渐近复杂性 第29页/共36页 第30页/共3

16、6页 渐近意义下的记号：O、o 设f(N)和g(N)是定义在正数集上的正函数。 O O的定义的定义：如果存在正的常数C和自然数N0，使得当NN0时有 f(N)Cg(N)，则称函数f(N)当N充分大时上有界，且g(N)是它的一 个上界，记为f(N)=O(g(N)。即f(N)的阶不高于g(N)的阶。 根据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)。 第31页/共36页 的定义的定义：如果存在正的常数C和自然数N0，使得当NN0时 有f(N)Cg(N)，则称函数f(N)当N充分大时下有界，且g(N)是它 的一