算法概述概要.pptx

算法设计与分析导论算法设计与分析导论 R.C.T.Lee S.S.TsengR.C.Chang著，王卫东译著，王卫东译 机械工业出版社机械工业出版社第第1章章 算法概述算法概述学习要点学习要点:理解算法的概念。理解什么是程序，程序与算法的区别和内在联系。掌握算法的计算复杂性概念。掌握算法渐近复杂性的数学表述。掌握用java语言描述算法的方法。电子计算机的出现是本世纪的一件大事，因为它改变了我们这个世界的面貌。可以毫不夸张地这么说，今天人们依赖于计算机，就象人们依赖于电力，如果它暂停了，社会就无法运转。快速电子计算机贵在神速，也就是它的运算速度快，同时它的发展之迅速也是惊人的。从每秒5000次运算，发展到现在的运算速度每秒数千亿次运算。元器件从继电器、真空管、晶体管、集成电路、大规模集成电路，发展到超大规模集成电路。结构上从每台机器作为运算工具的“单兵作战”模式，发展到今天将范围遍及各大洲的计算机网络，算法也从单机的串行计算发展到网络上并行的分布计算。一台作109次/秒运算（1G）的计算机的效率超过10亿人同时工作。它可以作中期的天气预报，可以控制庞大的化工厂生产过程，以至于还可以驾驭现代化战争，从这个意义上来说它确实是近乎神奇的。不过必须强调的是这些都是在人的安排下进行工作的。比如人们利用计算机作天气预报，必须依据天气变化规律，作出它的偏微分方程数学模型，以及编好程序，指导计算机按照人的安排一步步地工作，计算预报数据，绘制气象云图。这就是说，计算机虽然神通广大，还是在人的控制下工作。同时还应说明计算机并非什么都能做，有的事情理论上它根本做不了。讨论哪些事计算机能做，哪些事计算机做不了，属于可计算性理论研究的范畴。还有一些问题理论上计算机虽是能做，但实际上又是不可能完成的。比如拿最简单例子，26个英文字母全排列，它的排列数为：26！41026以每年365天计算，共有 3652436003.1536107秒以每秒能完成107个排列的超高速电子计算机来做这项工作，需要 41026/(3.15361014)1.21012年即使计算机运行速度随着技术的提高，恐怕也还是不可能实现的。因计算机的速度再提高也有它的极限。任何一项计算，总要事先拟定计算方案和规划计算步骤。为使计算机的计算过程能够解决某一问题，必须为计算机设计执行的解决方案中的每个详细步骤，并且将此过程完整地描述出来。所谓算法是对某个问题求解方案的完整而明确的描述。与算法有关的还有一个大家熟悉的公式：程序程序=算法十数据结构算法十数据结构 也就是说，算法设计和程序设计是不完全相同的。由于数字计算机运算速度很高，是人工手算所不能比拟的。为了充分发挥计算机的这种优点，在用计算机求解问题过程中，应尽量减少人工干预。因此，必须先将所制定的解决方案“告诉”计算机，使计算机按照人们规定的计算顺序去自动执行。用计算机能接受的“语言”来描述解题步骤，这项工作叫做程序设计，它还包含了需要使用合适的数据结构。“算法设计与分析”是研究算法的一门学科。它还很年轻远未定型，还处在发展中。有人说“计算机科学是一门研究算法的科学”。不论这个说法是否全面，算法无疑是计算机科学的重要组成部分。它近来发展极其迅速。“算法设计与分析”已是计算机专业本科生的一门必需掌握的内容。1.1.一些有趣的问题一些有趣的问题(1)巡回推销员问题巡回推销员问题:设有n个城市，已知任意两城市间之距离，现有一推销员想从某一城市出发巡回经过每一城市（且每城市只经过一次），最后又回到出发点，问如何找一条最短路径。设距离矩阵如下：试一试求出最短路径。（2)2)皇皇后后问问题题:这是高斯1850年提出的一个著名问题：国际象棋中的“皇后”在横向、直向、和斜向都能走步和吃子，问在nn 格的棋盘上如何能摆上n个皇后而使她们都不能互相吃。当n很大时，问题很难。对于n=8,现已知此问题共有92种解，但只有12种是独立的，其余的都可以由这12种利用对称性或旋转而得到。设n=4，试一试。(3(3）设天平有一些25克的砝码，一些10克的砝码，一些5克的砝码和一些1克的砝码。现要称63克的物体，问至少需要用几个砝码。(4(4）背背包包问问题题1 1：有一旅行者要从n种物品中选取不超过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的背包，问选择哪几个物体装入背包可以使其装的最满。（6 6）装装箱箱问问题题：设有体积分别为v1,v2,vn的n种物品u1,u2,un装到容量为L的箱子里。不同的装箱方案所需的箱子数目可能不同，问如何装箱能装完这n种物品且使用的箱子数目最少。（7 7）平平面面图图的的四四色色猜猜想想问问题题：一个平面图是否用四种颜色就可使相邻的区域颜色都不相同？2 2研究算法的重要性研究算法的重要性 假设某一负责人交给你一个很难的任务，几天后询问你问题解决了没有。可能会发生如下图这样的情况：问：“交给你的问题，解决方案设计出来了吗？”答：“我找不到一个有效的算法来解决它，没能完成任 务。”问：“交给你的问题，解决方案设计出来了吗？”答：“我找不到一个有效的算法来解决它，因为 这样的算法是不存在的。”(不过，要证明一个问题不存在有效算法，往往跟寻找有效算法一样难。)问：“交给你的问题，解决方案设计出来了吗？”答：“我找不到一个有效的算法来解决它，但不是 我不行，因为所有这些名人也都找不到解决它 的有效算法。”如果是你的话，你愿意是哪种结果？3.3.问题解决的好吗？问题解决的好吗？设计出解决问题的算法后，要知道算法的优劣好坏，是好算法则不必对其怀疑而再浪费时间进行研究。不是好算法则应再进行研究改进。而如何知道算法的优劣好坏，需要学习分析算法的方法。要设计出好算法，需要学习算法设计的常用方法。算法算法(Algorithm)v算法是指解决问题的一种方法或一个过程。v算法是若干指令的有穷序列，满足性质：v(1)输入输入：有外部提供的量作为算法的输入。v(2)输出输出：算法产生至少一个量作为输出。v(3)确定性确定性：组成算法的每条指令是清晰，无歧义的。v(4)有限性有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。程序程序(Program)v程序是算法用某种程序设计语言的具体实现。v程序可以不满足算法的性质(4)。v例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。v操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。问题求解问题求解(Problem Solving)证明正确性分析算法设计程序理解问题精确解或近似解选择数据结构算法设计策略设计算法分析算法的一些原则分析算法的一些原则v分析一个算法的优劣，主要考虑以下几个方面的问题：v 正确性正确性v 也即要求该算法在合理的输入数据下，能在有限的时间中得出正确的结果。分析算法的正确性，一般需要用到有关的数学定理（例如线性代数、图论、组合数学等方面的定理）。对于长的程序，可以将其分成一些小段来分析，只有每个小段都是正确的，才能保证整个程序的正确性。在分析算法的正确性时，数学归纳法是很有用的。运算工作量运算工作量v 此处并非指的是计算机真正的运算时间，因为这因计算机而异，也不是指需要执行的指令和语句数目，因为这与所用的程序语言和程序员的习惯有关。此处是分析算法本身的特点，我们希望有一个足够准确又足够一般的衡量方法，通常是计算所需的一些基本运算的次数。例如所需的比较次数，所需的加法和乘法次数等。而且通常是对不同的算法进行相对的比较。在分析比较算法时，运算量是一个非常重要的因素。所占空间量所占空间量v 这也不是具体指真正占多少计算机的内存或外存，因为这同样与所采用的计算机所用的程序语言和程序员惯用的格式有关。此处也是进行相对的比较。如果输入数据有其固有的形式，则我们分析还需要占多少额外的单元。当所需额外存储单元数不随输入数据的规模变化时，我们称这种算法是“就地”进行运算的（例如排序算法中的堆阵排序），对于大型的问题这当然比所需额外单元与输入数据规模大小有关的算法（如合并排序）要优越。应说明，这里所说“存储单元”，并无严格的定义，是因问题而异的。如果输入数据可以表示成不同的形式，例如图就有不同的表示方法，则还需要比较输入数据的不同形式占空间的多少。简单性简单性v 最简单最直接的方法往往不是最有效的方法，例如递归算法虽然简单，但运算工作量较大。但算法的简单性使得证明其正确性比较容易，编写程序、改错和修改程序都比较方便，可以节省人的时间，还是应当强调的。即使如此，对于经常使用的程序来说，算法的效率还是比其简单性更重要。算法的复杂性算法的复杂性v 复杂性是指实现和运行一算法所需资源的多少，包括时间复杂性（所需运算时间），空间复杂性（所占存储空间）和人工复杂性（编程改错等所需人工）。我们研究的重点是时间复杂性。v 算法的各个复杂性可以用一个变量表示，这个变量就是问题实例的“规模”，用它反映描述该实例所需要输入的数据总量。这样做是方便的，因为预料问题实例的相对难度随着它们的规模而变化。v 我们用n作为表示问题规模的量，例如排序问题中n为需要排序的元素的个数；图的问题中n为图的顶点数或边数；矩阵求逆中n为矩阵的阶数等。评定算法优劣的标准要看它的时间复杂性、空间复杂性和人工复杂性，其中时间复杂性最为重要，通常是用它来衡量某个算法的“好”或“坏”。不同的算法具有很不相同的时间复杂性函数，说它们当中哪些“效率足够高”哪里“效率太低”，总要看当时的情况。但是，计算机科学家们公认一种简单的区别，这种区别对这些问题提供了重要的透彻的分析，这就是多项式时间算法和非多项式时间算法之间的区别。时间复杂性则表成n的函数T(n)。下表表示各种 T(n)的算法在不同的n值时的运算时间。不同时间复杂性函数的对比 可以看出，不同T(n)的算法当n增长时运算时间增长的快慢很不同。T(n)为指数形式的算法当n较大时实际上是无法应用的。有些算法T(n)与n！成正比，它随n的加大比指数函数增长还要快，这种算法更是没有实用价值。凡是T(n)为n的对数函数、线性函数或多项式的(幂函数也是多项式的特例)，我们称这类算法为“有效算法”，或好的算法；反之，凡是T(n)为指数函数或阶乘函数的，称之为坏的算法。提高计算速度对不同时间复杂性函数的影响对比 为了分析方便，复杂性通常用数量级的形式表示。如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!)。算法复杂性是算法运行所需要的计算机资源的量，需要时间资源的量称为时间复杂性时间复杂性，需要的空间资源的量称为空间复杂性空间复杂性。这个量应该只依赖于算法要解的问题的规模、算法的输入和算法本身的函数。如果分别用N、I和A表示算法要解问题的规模、算法的输入和算法本身，而且用C表示复杂性，那么，应该有C=F(N,I,A)。一般把时间复杂性和空间复杂性分开，并分别用T和S来表示，则有：T=T(N,I)和S=S(N,I)。（通常，让A隐含在复杂性函数名当中）最坏情况下的时间复杂性：最好情况下的时间复杂性：平均情况下的时间复杂性：其中DN是规模为N的合法输入的集合；I*是DN中使T(N,I*)达到Tmax(N)的合法输入；是中使T(N,)达到Tmin(N)的合法输入；而P(I)是在算法的应用中出现输入I的概率。算法渐近复杂性算法渐近复杂性算法渐近复杂性算法渐近复杂性vT(n),as n;v(T(n)-t(n)/T(n)0，as n;vt(n)是T(n)的渐近性态，为算法的渐近复杂性。v在数学上，t(n)是T(n)的渐近表达式，是T(n)略去低阶项留下的主项。它比T(n)简单。渐近意义下的记号：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)。算法渐近复杂性算法渐近复杂性 的定义的定义：如果存在正的常数C和自然数N0，使得当NN0时有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)同阶。o o的定义的定义：对于任意给定的0，都存在正整数N0，使得当NN0时有f(N)/Cg(N),则称函数f(N)当N充分大时的阶比g(N)低，记为f(N)=o(g(N)。例如，4NlogN+7=o(3N2+4NlogN+7)。算法渐近复杂性算法渐近复杂性算法分析中常见的复杂性函数算法分析中常见的复杂性函数最优算法最优算法v问题的计算时间下界为(f(n)，则计算时间复杂性为O(f(n)的算法是最优算法。v例如，排序问题的计算时间下界为(nlogn)，计算时间复杂性为O(nlogn)的排序算法是最优算法。v堆排序算法是最优算法。课后作业（1）假设某算法在输入规模为n使得计算时间为T(n)=3*2n，在某台计算机上实现并完成该算法的时间为t秒。现有令一台计算机，其运行速度为第一台的64倍，那么在这台新机器上用同一算法在t秒内能解输入为多大的问题。（2）若上述算法的计算时间改进为T(n)=n2，其余条件不变，则在新机器上用t秒时间内能解输入为多大的问题。（3）若上述算法的计算时间进一步改进为T(n)=8，其余条件不变，则在新机器上用t秒时间内能解输入为多大的问题。