算法设计第一章

课程目的：计算机算法设计与分析导引以算法设计为主，介绍算法设计的主要方法和基本思想；并简要介绍算法分析概念不是程序设计课，也不是数学课主要内容：算法复杂性分析方法：蛮力法、递归与分治、减治法、动态规划、贪心法。算法设计与分析第1章算法概述本章主要知识点：1.1算法与程序1.2算法问题求解基础1.3重要问题类型1.4基本数据结构1.5算法分析的基本原则1.6算法复杂性分析1.1算法与程序算法：是满足下述性质的指令序列。输入：有零个或多个外部量作为算法的输入。输出：算法产生至少一个量作为输出。确定性：组成算法的每条指令清晰、无歧义。有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。程序：程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质(4)即有限性。例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。1.1算法与程序算法的概念问题↓算法↓输入→computer→输出同一算法可以用几种不同的形式来描述同一问题，可能存在几种不同的算法，不同算法解题速度也会有所不同。例子：求两个不全为0的非负整数m和n的最大公约数记为gcd(m,n)欧几里德算法//输入：两个不全为0的非负整数m,n//输出：m,n的最大公约数Whilen≠0dor←mmodnm←nn←rReturnm中学里学过的计算方法找到m,n的所有质因数从上述质因数分解式中找出所有公因数（如果p是一个因数，而且在m和n的质因数分解式中分别出现x和y次，则将p重复min{x.y}次将上述找到的质因数相乘，其结果作为最大公约数1.2算法问题求解基础算法＋数据结构＝程序算法设计分析的主要步骤理解问题了解计算设备的性能在精确算法和近似算法之间做出选择确定适当的数据结构算法的设计技术算法的描述（伪代码）算法的正确性证明算法的分析（简单性、一般性）1.3重要问题类型排序查找字符串处理图问题（图的遍历算法、最短路线算法、图着色问题）组合问题几何问题（最接近点对问题、凸包问题）数值问题（具有连续性的数学问题：解方程、定积分、求函数值）1.4基本数据结构数据结构：对相关的数据项进行组织的特殊方案。算法与数据结构的关系不了解施加于数据上的算法就无法决定如何构造数据，可以说算法是数据结构的灵魂；反之算法的结构和选择又常常在很大程度上依赖于数据结构，数据结构则是算法的基础。线性数据结构（数组和链表）、图（加权图、路径和环）、树（有根数、二叉树）、集合与字典1.4表达算法的抽象机制2.抽象数据类型抽象数据类型是算法的一个数据模型连同定义在该模型上并作为算法构件的一组运算。抽象数据类型带给算法设计的好处有：1)算法顶层设计与底层实现分离；2)算法设计与数据结构设计隔开，允许数据结构自由选择；3)数据模型和该模型上的运算统一在ADT中，便于空间和时间耗费的折衷；4)用抽象数据类型表述的算法具有很好的可维护性；5)算法自然呈现模块化；6)为自顶向下逐步求精和模块化提供有效途径和工具；7)算法结构清晰，层次分明，便于算法正确性的证明和复杂性的分析。1.4描述算法与算法设计问题求解(ProblemSolving)证明正确性分析算法设计程序理解问题精确解或近似解选择数据结构算法设计策略设计算法1.5算法分析的基本原则1.正确性定义：在给定有效输入后，算法经过有限时间的计算并产生正确的答案，就称算法是正确的。正确性证明的内容：方法的正确性证明——算法思路的正确性。证明一系列与算法的工作对象有关的引理、定理以及公式。程序的正确性证明——证明所给出的一系列指令确实做了所要求的工作。程序正确性证明的方法：大型程序的正确性证明——可以将它分解为小的相互独立的互不相交的模块，分别验证。小模块程序可以使用以下方法验证：数学归纳法、软件形式方法等。1.5算法分析的基本原则2.工作量——时间复杂性分析计量工作量的标准:对于给定问题，该算法所执行的基本运算的次数。基本运算的选择：根据问题选择适当的基本运算。问题基本运算在表中查找x比较实矩阵相乘实数乘法排序比较遍历二叉树置指针1.5算法分析的基本原则3.占用空间——空间复杂性分析两种占用：存储程序和输入数据的空间存储中间结果或操作单元所占用空间——额外空间影响空间的主要因素：存储程序的空间一般是常数(和输入规模无关)输入数据空间为输入规模O(n)空间复杂性考虑的是额外空间的大小如果额外空间相对于输入规模是常数，称为原地工作的算法。1.5算法分析的基本原则4.简单性含义：算法简单，程序结构简单。好处：容易验证正确性便于程序调试简单的算法效率不一定高。要在保证一定效率的前提下力求得到简单的算法。1.5算法分析的基本原则5.最优性含义：指求解某类问题中效率最高的算法两种最优性最坏情况：设A是解某个问题的算法，如果在解这个问题的算法类中没有其它算法在最坏情况下的时间复杂性比A在最坏情况下的时间复杂性低，则称A是解这个问题在最坏情况下的最优算法。平均情况：设A是解某个问题的算法，如果在解这个问题的算法类中没有其它算法在平均情况下的时间复杂性比A在平均情况下的时间复杂性低，则称A是解这个问题在平均情况下的最优算法。寻找最优算法的途径(以最坏情况下的最优性为例)设计算法A，求W(n)。相当于对问题给出最坏情况下的一个上界。寻找函数F(n)，使得对任何算法都存在一个规模为n的输入并且该算法在这个输入下至少要做F(n)次基本运算。相当于对问题给出最坏情况下所需基本运算次数的一个下界。如果W(n)=F(n)，则A是最优的。如果W(n)F(n)，A不是最优的或者F(n)的下界过低。改进A或设计新算法A’使得W’(n)W(n)。重新证明新下界F’(n)使得F’(n)F(n)。重复以上两步，最终得到W’(n)=F’(n)为止。1.5算法分析的基本原则例：在n个不同的数中找最大的数。基本运算：比较算法：FindMax输入：数组L，项数n11输出：L中的最大项MAX1)MAX←L(1);i←2;2)whilei≤ndo3)ifMAXL(i)thenMAX←L(i);4)i←i+1;5)end。行3的比较进行n－1次，故W(n)=n－1。定理：在n个数的数组中找最大的数，并以比较作为基本运算的算法类中的任何算法最坏情况下至少要做n－1次比较。结论：FindMax算法是最优算法。1.6算法复杂性分析算法复杂性是算法运行所需要的计算机资源的量，需要时间资源的量称为时间复杂性，需要的空间资源的量称为空间复杂性。这个量应该只依赖于算法要解的问题的规模、算法的输入和算法本身的函数。如果分别用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.6算法复杂性分析NNNNNNDIkiiiDIavgkiiikiiiDIDIMinkiiikiiiDIDIMaxINetIPINTIPNTINTINetINetINTNTINTINetINetINTNT11111),()(),()()()~,()~,(),(min),(min)(*),(*),(),(max),(max)(以上分别是最坏情况下、最好情况下和平均情况下的时间复杂性。其中DN是规模为N的合法输入的集合；I*是DN中使T(N,I*)达到TMax(N)的合法输入；I-是DN中使T(N,I-)达到TMin(N)的合法输入；而P(I)是在算法的应用中出现输入I的概率。1.6算法复杂性分析函数的渐进性态与渐进表达式：一般来说，当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。1.6算法复杂性分析算法复杂性在渐近意义下的阶：渐近意义下的记号：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)。1.6算法复杂性分析Ω的定义：如果存在正的常数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)。的定义：(g(n))={f(n)|对于任何正常数c0，存在正数和n00使得对所有n≥n0有：0≤cg(n)＜f(n)}等价于f(n)/g(n)，asn。f(n)(g(n))g(n)o(f(n))1.6算法复杂性分析渐近分析记号的若干性质（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))。1.6算法复杂性分析规则Ｏ(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)。令c