算法设计-第一章

计算机算法设计与分析（第3版）王晓东编著电子工业出版社算法设计与分析引论1．关于用计算机解决问题1.1计算机的能力电子计算机的出现是本世纪的一件大事，因为它改变了我们这个世界的面貌。可以毫不夸张地这么说，今天人们依赖于计算机，就象人们依赖于电力，如果它暂停了，社会就无法运转。快速电子计算机贵在神速，也就是它的运算速度快，同时它的发展之迅速也是惊人的。从每秒5000次运算，发展到现在的运算速度每秒数千亿次运算。元器件从继电器、真空管、晶体管、集成电路、大规模集成电路，发展到超大规模集成电路。结构上从每台机器作为运算工具的“单兵作战”模式，发展到今天将范围遍及各大洲的计算机网络，算法也从单机的串行计算发展到网络上并行的分布计算。一台作109次/秒运算（1G）的计算机的效率超过10亿人同时工作。它可以作中期的天气预报，可以控制庞大的化工厂生产过程，以至于还可以驾驭现代化战争，从这个意义上来说它确实是近乎神奇的。不过必须强调的是这些都是在人的安排下进行工作的。比如人们利用计算机作天气预报，必须依据天气变化规律，作出它的偏微分方程数学模型，以及编好程序，指导计算机按照人的安排一步步地工作，计算预报数据，绘制气象云图。这就是说，计算机虽然神通广大，还是在人的控制下工作。同时还应说明计算机并非什么都能做，有的事情理论上它根本做不了。讨论哪些事计算机能做，哪些事计算机做不了，属于可计算性理论研究的范畴。还有一些问题理论上计算机虽是能做，但实际上又是不可能完成的。比如拿最简单例子，26个英文字母全排列，它的排列数为：26！≈4×1026以每年365天计算，共有365×24×3600＝3.1536×107秒以每秒能完成107个排列的超高速电子计算机来做这项工作，需要4×1026/(3.1536×1014)≈1.2×1012年即使计算机运行速度随着技术的提高，恐怕也还是不可能实现的。因此计算机的速度再提高也有它的极限。1.2用计算机解决问题的关键任何一项计算，总要事先拟定计算方案和规划计算步骤。为使计算机的计算过程能够解决某一问题，必须为计算机设计执行的解决方案中的每个详细步骤，并且将此过程完整地描述出来。所谓算法是对某个问题求解方案的完整而明确的描述。与算法有关的还有一个大家熟悉的公式：

程序=算法十数据结构也就是说，算法设计和程序设计是不完全相同的。由于数字计算机运算速度很高，是人工手算所不能比拟的。为了充分发挥计算机的这种优点，在用计算机求解问题过程中，应尽量减少人工干预。因此，必须先将所制定的解决方案“告诉”计算机，使计算机按照人们规定的计算顺序去自动执行。用计算机能接受的“语言”来描述解题步骤，这项工作叫做程序设计，它还包含了需要使用合适的数据结构。“算法设计与分析”是研究算法的一门学科。它还很年轻远未定型，还处在发展中。有人说“计算机科学是一门研究算法的科学”。不论这个说法是否全面，算法无疑是计算机科学的重要组成部分。它近来发展极其迅速。“算法设计与分析”已是计算机专业本科生的一门必需掌握的内容。1.3一些有趣的问题(1)巡回推销员问题:设有n个城市，已知任意两城市间之距离，现有一推销员想从某一城市出发巡回经过每一城市（且每城市只经过一次），最后又回到出发点，问如何找一条最短路径。设距离矩阵如下：试一试求出最短路径。úúúúúúûùêêêêêêëé=0186572641805673556556041772734103964557390D（2)皇后问题:这是高斯1850年提出的一个著名问题：国际象棋中的“皇后”在横向、直向、和斜向都能走步和吃子，问在n×n格的棋盘上如何能摆上n个皇后而使她们都不能互相吃。当n很大时，问题很难。对于n=8,现已知此问题共有92种解，但只有12种是独立的，其余的都可以由这12种利用对称性或旋转而得到。设n=4，试一试。

(3）设天平有一些25克的砝码，一些10克的砝码，一些5克的砝码和一些1克的砝码。现要称63克的物体，问至少需要用几个砝码。

(4）背包问题1：有一旅行者要从n种物品中选取不超过b公斤重的行李随身携带，要求总价值最大。例：设背包的容量为50千克。物品1重10千克，价值60元；物品2重20千克，价值100元；物品3重30千克，价值120元。求总价值最大。（5）背包问题2：设有n=8个体积分别为54，45，43，29，23，21，14，1的物体和一个容积为C=110的背包，问选择哪几个物体装入背包可以使其装的最满。

（6）装箱问题：设有体积分别为v1,v2,…,vn的n种物品u1,u2,…,un装到容量为L的箱子里。不同的装箱方案所需的箱子数目可能不同，问如何装箱能装完这n种物品且使用的箱子数目最少。

（7）平面图的四色猜想问题：一个平面图是否用四种颜色就可使相邻的区域颜色都不相同？2.算法设计的重要性算法是计算机科学的灵魂美国计算机科学家唐纳德·克努斯(DonaldKnuth,中文名：高德纳

)

经典巨著《计算机程序设计艺术

》，第一卷《《基本算法》，获得图灵奖。比尔·盖茨曾经花了几个月的时间读完这一卷，并且做了大量的练习，然后他说，如果你想成为一个优秀的程序员，那就去读这个《基本算法》吧。高德纳本人的说法更犀利：要是看不懂，就别当程序员。ACM’sTuringAwards1966年至1999年的图灵奖获得者中有12人直接或间接地与算法相关：D.E.Knuth,M.O.RabinandD.S.Scott,R.W.Floyd,C.A.R.Hoare,S.A.Cook,N.Wirth,R.M.Karp,J.E.HopcrftandR.E.Steams,M.Blum,etc.二十世纪算法的三大发现：快速傅里叶变换：使数字信号处理、数字通信等技术成为现实最短路径算法：在许多领域尤其是计算机网络领域起重要作用距阵乘法：打破了距阵相乘的O(n3)的界限3.课程信息:GoalAsurveyofalgorithmicdesigntechniques.Abstractthinking.Howtodevelopnewalgorithmsforanyproblemthatmayarise.Beagreatthinkeranddesigner.Not:Alistofalgorithms-Learntheircode-Tracethemuntilwork-Implimentthem-beamundaneprogrammer培养良好的软件开发习惯，即在软件开发过程中要考虑：能不能解决这个问题？一个算法有多好?还能更好吗?4.课程内容:介绍计算机应用领域提出的一些算法和计算复杂性的基本原理。先修课程：数据结构，c或c++编程主要内容：第一章算法概述第二章递归与分治策略第三章动态规划第四章贪心算法第五章回溯法第六章分支限界法5.参考教材1.计算机算法设计与分析（第三版），电子工业出版社，2007，王晓东2.《算法设计技巧与分析》，电子工业出版社，2004.3.计算机算法基础（第二版），余祥宣、崔国华、邹海明，华中科技大学出版社，2002.14.算法设计与分析基础（第二版），清华大学出版社，莱维丁著，潘彦译第1章算法概述学习要点:理解算法的概念。理解什么是程序，程序与算法的区别和内在联系。掌握算法的计算复杂性概念。掌握算法渐近复杂性的数学表述。掌握用C++语言描述算法的方法。1.1算法与程序算法是指解决问题的一种方法或一个过程。算法是若干指令的有穷序列，满足性质：(1)输入：有外部提供的量作为算法的输入。(2)输出：算法产生至少一个量作为输出。(3)确定性：组成算法的每条指令是清晰，无歧义的。(4)有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。(5)可行性：算法(Algorithm)程序(Program)程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质(4)。例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。问题求解(ProblemSolving)证明正确性分析算法设计程序理解问题精确解或近似解选择数据结构算法设计策略设计算法正确性定义：在给定有效输入后，算法经过有限时间的计算并产生正确的答案，就称算法是正确的。正确性证明的内容：方法的正确性证明——算法思路的正确性。证明一系列与算法的工作对象有关的引理、定理以及公式。程序的正确性证明——证明所给出的一系列指令确实做了所要求的工作。程序正确性证明的方法：大型程序的正确性证明——可以将它分解为小的相互独立的互不相交的模块，分别验证。小模块程序可以使用以下方法验证：数学归纳法、软件形式方法等。衡量算法性能一般有下面几个标准2.易读性3.健壮性4.算法的时间和空间性能：高效率和低存储空间1.2算法分析(AlgorithmAnalysis)算法分析：对于算法的时间和空间复杂度进行定量分析。分析算法时间复杂度的基本步骤算法时间复杂度的有关概念分析、求解算法复杂度的基本方法算法复杂性是算法运行所需要的计算机资源的量，需要时间资源的量称为时间复杂性，需要的空间资源的量称为空间复杂性。这个量应该只依赖于算法要解的问题的规模、算法的输入和算法本身的函数。如果分别用N、I和A表示算法要解问题的规模、算法的输入和算法本身，而且用C表示复杂性，那么，应该有C=F(N,I,A)。一般把时间复杂性和空间复杂性分开，并分别用T和S来表示，则有：T=T(N,I)和S=S(N,I)。（通常，让A隐含在复杂性函数名当中）算法复杂性分析

算法复杂性=算法所需要的计算机资源算法的时间复杂性T(n)；算法的空间复杂性S(n)。其中n是问题的规模（输入大小）。1.空间复杂性分析两种占用：存储程序和输入数据的空间存储中间结果或操作单元所占用空间——额外空间影响空间的主要因素：存储程序的空间一般是常数(和输入规模无关)输入数据空间为输入规模O(n)空间复杂性考虑的是额外空间的大小如果额外空间相对于输入规模是常数，称为原地工作的算法。2.时间复杂性分析计量工作量的标准:对于给定问题，该算法所执行的基本运算的次数。通常用渐进形式表示比如，T(n)=Ο(n2)、Ω

(n2)或θ(n2)基本运算的选择：根据问题选择适当的基本运算。问题基本运算在表中查找x比较实矩阵相乘实数乘法排序比较遍历二叉树置指针3.分析时间复杂度的基本步骤一、选取一种运算作为基本运算二、表示出在算法运行期间基本运算执行的总频数三、渐近时间复杂度（asymptotictimecomplexity）函数的渐进性态与渐进表达式：一般来说，当N单调增加且趋于∞时，T(N)也将单调增加趋于∞。对于T(N)，如果存在函数T'(N)，使得当N→∞使有(T(N)-T'(N))/T(N)→0，那么我们就说T'(N)是T(N)当N→∞时的渐进性态。在数学上，T'(N)是T(N)当N→∞时的渐进表达式。例如：3N2+4NlogN+7与3N2。算法渐近复杂性T(n)

,asn

;(T(n)-t(n))/T(n)0，asn;t(n)是T(n)的渐近性态，为算法的渐近复杂性。在数学上，t(n)是T(n)的渐近表达式，是T(n)略去低阶项留下的主项。它比T(n)简单。算法复杂性分析算法复杂性在渐近意义下的阶：渐近意义下的记号：O、Ω、θ、o

设f(N)和g(N)是定义在正数集上的正函数。O的定义：如果存在正的常数C和自然数N0，使得当N

N0时有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)。

规则Ｏ(f(n))+Ｏ(g(n))=Ｏ(max{f(n),g(n)})的证明：对于任意f1(n)∈Ｏ(f(n))，存在正常数c1和自然数n1，使得对所有n≥n1，有f1(n)≤c1f(n)。类似地，对于任意g1(n)∈Ｏ(g(n))，存在正常数c2和自然数n2，使得对所有n≥n2，有g1(n)≤c2g(n)。令c3=max{c1,c2}，n3=max{n1,n2}，h(n)=max{f(n),g(n)}。则对所有的n≥n3，有f1(n)+g1(n)≤c1f(n)+c2g(n)≤c3f(n)+c3g(n)=c3(f(n)+g(n))≤c32max{f(n),g(n)}＝2c3h(n)＝Ｏ(max{f(n),g(n)}).算法复杂性分析Ω的定义：如果存在正的常数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)同阶。o的定义：对于任意给定的ε＞0，都存在正整数N0，使得当N

N0时有f(N)/Cg(N)

ε,则称函数f(N)当N充分大时的阶比g(N)低，记为f(N)=o(g(N))。例如，4NlogN+7=o(3N2+4NlogN+7)。

渐近分析记号的若干性质（1）传递性：f(n)=θ(g(n))，g(n)=θ(h(n))→f(n)=θ(h(n))；f(n)=Ｏ(g(n))，g(n)=Ｏ(h(n))→f(n)=Ｏ(h(n))；f(n)=Ω(g(n))，g(n)=Ω(h(n))→f(n)=Ω(h(n))；f(n)=ｏ(g(n))，g(n)=ｏ(h(n))→f(n)=ｏ(h(n))；f(n)=ω(g(n))，g(n)=ω(h(n))→f(n)=ω(h(n))；（2）反身性：f(n)=θ(f(n))；f(n)=Ｏ(f(n))；f(n)=Ω(f(n)).（3）对称性：f(n)=θ(g(n))<==>g(n)=θ(f(n)).（4）互对称性：f(n)=Ｏ(g(n))<==>g(n)=Ω(f(n))；f(n)=ｏ(g(n))<==>g(n)=ω(f(n))；（5）算术运算：Ｏ(f(n))+Ｏ(g(n))=Ｏ(max{f(n),g(n)})；Ｏ(f(n))+Ｏ(g(n))=Ｏ(f(n)+g(n))；Ｏ(f(n))*Ｏ(g(n))=Ｏ(f(n)*g(n))；Ｏ(cf(n))=Ｏ(f(n))；g(n)=Ｏ(f(n))→Ｏ(f(n))+Ｏ(g(n))=Ｏ(f(n))。渐近表示—Examples[例1]设f(n)=10n2+20n。则有f(n)=O(n2)f(n)=Ω(n2)f(n)=θ(n2)[例2]设f(n)=aknk+ak-1nk-1+…+a1n+a0,(ak>0)。则有f(n)=O(nk)f(n)=

Ω

(nk)：f(n)=θ

(nk)由此可见，复杂度的渐近表示可以简洁地表示出复杂度的数量级别。对于算法的时间复杂度，通常从分平均、最坏、最好几种情形来衡量，尤其是前两种。算法的平均复杂性算法的最坏复杂性算法的最好复杂性算法的时间复杂性的有关概念（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出现的概率。[例1]检索问题的顺序查找算法以元素的比较作为基本操作。考虑成功检索的情况。最好情况下的时间复杂度：θ

(1)最坏情况下的时间复杂度：θ

(n)在等概率前提下，平均情况下的时间复杂度：θ

(n)[例2]直