第一章：算法概述

算法分析与设计

AlgorithmDesign&Anlysis

关于本课程课程目的：计算机算法设计与分析导引以算法设计为主，介绍算法设计的主要方法和基本思想；并简要介绍算法分析概念不是程序设计课，也不是数学课参考资料：Web资源图书资源《数据结构》与《算法设计与分析》课程的关系从考虑问题的角度来看，数据结构主要关心不同的数据结构在计算机解题中的作用和效率；而算法设计与分析则关心不同的算法设计技术的适用性和效率。这使得这两门课程在某种程度上有所重叠，但又无法相互替代。从考虑问题的高度来看，数据结构关心的是计算机解题的具体问题，所以很适合作为计算机的入门课程之一；但算法设计与分析则要宽泛地多，很适合计算机专业的学生学习，但又不仅限于解决计算机解题的问题。“授人以鱼，不如授人以渔”当把算法设计与分析提升为一种解决问题的通用方法时，学习它会有很大收获，而且可能终身受益。算法在CS中占有重要地位有超过1/3的Turing奖获奖者(22/57)，其成果与算法有关。图灵奖于1966年开始设立，是ACM（美国计算机协会）在计算机科学技术领域中所授予的最高奖项。1972，EdsgerW.Dijkstra(美Burroughs公司)：求最短路径的Dijkstra算法，PV操作，结构化程序设计，“goto有害”等。1974，DonaldE.Knuth(stanford)：多卷算法巨著(算法最早的奠基人之一)，现代“算法”与“数据结构”名词及内涵的提出，KMP算法，LR(k)文法，Tex编辑器等。

1976，MichaelO.Rabin(以色列)&DanaS.Scott(英)师兄弟：非确定有穷自动机的提出、判定问题等。Rabin：计算复杂性概念的雏形、随机算法的思想奠定、寻找及判定素数算法，单向函数等。Scott:语义学等。1978，RobertW.Floyd(美)：算法(求最短路径的Floyd动态规划算法，Heap-sort算法等)，编译及优化(优先文法等)，程序正确性证明等。1980，C.AnthonyR.Hoare(英)：ACM评出的1/4世纪中最有影响的25篇论文：Hoare与Dijkstra有两篇入选(其余人只有一篇)。算法的代表作：Quick-sort算法，程序设计(CASE、While语句等)，数据通信等。1982，StevenA.Cook(加Toronto大学)：“NP-完全”概念的提出与理论的奠定，算法复杂性。1984，NiklausWirth(瑞士苏黎世高工)：“程序=算法+数据结构”，结构化程序设计创始人，“Pascal之父”,数据结构，ExtendedBNF等。1985，RichardM.Karp(UC-Berkeley)：计算机系、数学系、工业工程与运筹学系“三栖教授”，哈佛文学士、理学硕士、数学博士。分枝限界法的创始人(与Held)，Rabin-Karp子串匹配算法，求网络最大流的Edmonds-Karp算法，NP-完全理论(Karp规约等)，随机算法，并行算法等。1986，JohnE.Hopcroft(Cornell)&Robert

E.Tarjan

(Princeton)：图论算法(e.g.深度优先、广度优先算法、连通性、平面图判定)，各种数据结构Hopcroft：Aho书作者之一，形式语言与自动机名著(与Ullman)，算法好坏的衡量尺度(渐进时间复杂性)，2-3树，机器人等。Tarjan：D.E.Knuth的博士生，集合的Union-find算法，平摊分析，持久性数据结构及各种数据结构(e.g.动态树、”八字型”树，自调整结构)1993，JurisHartmanis&RichardE.Stearns：计算复杂性理论的主要奠基人：系统化的理论体系及命名。Hartmanis：Hartmanis矩阵乘法，Hartmanis快速离散傅立叶变换Stearns：首先提出将上下文无关文法理论应用于编译器设计等。1995，ManuelBlum(UC-Berkeley)：计算复杂性理论(受M.O.Rabin到MIT演讲的启发)，e.g.Blum测度等；复杂性理论应用(e.g.密码学、软件工程)。2000，AndrewYao(姚期智)：唯一的华裔图灵奖获得者计算复杂性，量子计算，密码学(e.g.单向函数)、通信理论等。2002，RonaldL.Rivest，AdiShamir，LeonardM.Adelman:公共密钥算法(RSA算法是当前在互联网传输、银行以及信用卡产业中被广泛使用的安全基本机制).

92007，EdmundClarke(美），AllenEmerson（美），JosephSifakis（法）分别提出了模型检测的最初概念，开发了一套用于判断硬件和软件设计的理论模型是否满足规范的方法，此外，当系统检测失败时，还能利用它确定代码中问题存在的位置。2010，LeslieG.Valiant(英)主要贡献之一是PAC模型（ProbablyApproximatelyCorrect，概率近似正确），该模型可解决信息分类的问题，可最大限度的降低泛化带来的错误，对于及其学习、人工智能（如自然语言处理、笔迹识别、机器视觉等）都产生了重要影响。第1章算法概述本章主要知识点：1.1算法与程序1.2算法与数据结构1.3表达算法的抽象机制1.4描述算法与算法设计1.5算法分析的基本原则1.6算法复杂性分析1.1 算法与程序算法：是满足下述性质的指令序列。输入：有零个或多个外部量作为算法的输入。输出：算法产生至少一个量作为输出。确定性：组成算法的每条指令清晰、无歧义。有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。程序：程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质(4)即有限性。例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。1.2 算法与数据结构算法与数据结构的关系不了解施加于数据上的算法就无法决定如何构造数据，可以说算法是数据结构的灵魂；反之算法的结构和选择又常常在很大程度上依赖于数据结构，数据结构则是算法的基础。算法＋数据结构＝程序1.3 表达算法的抽象机制从机器语言到高级语言的抽象高级程序设计语言的主要好处是：高级语言更接近算法语言，易学、易掌握，一般工程技术人员只需要几周时间的培训就可以胜任程序员的工作；高级语言为程序员提供了结构化程序设计的环境和工具，使得设计出来的程序可读性好，可维护性强，可靠性高；高级语言不依赖于机器语言，与具体的计算机硬件关系不大，因而所写出来的程序可植性好、重用率高；把繁杂琐碎的事务交给编译程序，所以自动化程度高，开发周期短，程序员可以集中时间和精力从事更重要的创造性劳动，提高程序质量。1.3 表达算法的抽象机制抽象数据类型抽象数据类型是算法的一个数据模型连同定义在该模型上并作为算法构件的一组运算。抽象数据类型带给算法设计的好处有：算法顶层设计与底层实现分离；算法设计与数据结构设计隔开，允许数据结构自由选择；数据模型和该模型上的运算统一在ADT中，便于空间和时间耗费的折衷；用抽象数据类型表述的算法具有很好的可维护性；算法自然呈现模块化；为自顶向下逐步求精和模块化提供有效途径和工具；算法结构清晰，层次分明，便于算法正确性的证明和复杂性的分析。1.4 描述算法与算法设计描述算法可以有多种方式，如自然语言方式、图形表格方式等。在这里，我们将采用C++语言来描述算法。C++语言的优点是类型丰富、语句精炼，具有面向对象和面向过程的双重优点。用C++来描述算法可使整个算法结构紧凑、可读性强。在课程中，有时为了更好地阐明算法的思路，我们还采用C++与自然语言相结合的方式来描述算法。算法设计方法主要有：分治策略、动态规划、贪心算法、回溯法、分支限界、概率算法等，我们将在后面的章节中陆续介绍。1.4 描述算法与算法设计问题求解(ProblemSolving)证明正确性分析算法设计程序理解问题精确解或近似解选择数据结构算法设计策略设计算法1.5算法分析的基本原则正确性定义：在给定有效输入后，算法经过有限时间的计算并产生正确的答案，就称算法是正确的。正确性证明的内容：方法的正确性证明——算法思路的正确性。证明一系列与算法的工作对象有关的引理、定理以及公式。程序的正确性证明——证明所给出的一系列指令确实做了所要求的工作。程序正确性证明的方法：大型程序的正确性证明——可以将它分解为小的相互独立的互不相交的模块，分别验证。小模块程序可以使用以下方法验证：数学归纳法、软件形式方法等。1.5算法分析的基本原则工作量——时间复杂性分析计量工作量的标准:对于给定问题，该算法所执行的基本运算的次数。基本运算的选择：根据问题选择适当的基本运算。问题基本运算在表中查找x比较实矩阵相乘实数乘法排序比较遍历二叉树置指针1.5算法分析的基本原则占用空间——空间复杂性分析两种占用：存储程序和输入数据的空间存储中间结果或操作单元所占用空间——额外空间影响空间的主要因素：存储程序的空间一般是常数(和输入规模无关)输入数据空间为输入规模O(n)空间复杂性考虑的是额外空间的大小如果额外空间相对于输入规模是常数，称为原地工作的算法。1.5算法分析的基本原则简单性含义：算法简单，程序结构简单。好处：容易验证正确性便于程序调试简单的算法效率不一定高。要在保证一定效率的前提下力求得到简单的算法。1.5算法分析的基本原则最优性含义：指求解某类问题中效率最高的算法两种最优性最坏情况：设A是解某个问题的算法，如果在解这个问题的算法类中没有其它算法在最坏情况下的时间复杂性比A在最坏情况下的时间复杂性低，则称A是解这个问题在最坏情况下的最优算法。平均情况：设A是解某个问题的算法，如果在解这个问题的算法类中没有其它算法在平均情况下的时间复杂性比A在平均情况下的时间复杂性低，则称A是解这个问题在平均情况下的最优算法。1.5算法分析的基本原则例：在n个不同的数中找最大的数。基本运算：比较算法：FindMax输入：数组L，项数n输出：L中的最大项MAXMAX←L(1);i←2;whilei≤ndoifMAX<L(i)thenMAX←L(i);i←i+1;end。行3的比较进行n－1次，故W(n)=n－1。定理：在n个数的数组中找最大的数，并以比较作为基本运算的算法类中的任何算法最坏情况下至少要做n－1次比较。证：因为MAX是唯一的，其它的n－1个数必须在比较后被淘汰。一次比较至多淘汰一个数，所以至少需要n－1次比较。结论：FindMax算法是最优算法。算法分析的基本法则非递归算法：（1）for/while循环循环体内计算时间*循环次数；（2）嵌套循环循环体内计算时间*所有循环次数；（3）顺序语句各语句计算时间相加；（4）if-else语句if语句计算时间和else语句计算时间的较大者。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 算法复杂性分析以上分别是最坏情况下、最好情况下和平均情况下的时间复杂性。其中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的定义，容易证明它有如下运算规则：O(f)+O(g)=O(max(f,g))；O(f)+O(g)=O(f+g)；O(f)O(g)=O(fg)；如果g(N)=O(f(N))，则O(f)+O(g)=O(f)；O(Cf(N))=O(f(N))，其中C是一个正的常数；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)|对于任何正常数c>0，存在正数和n0>0使得对所有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)。令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)}).1.6 算法复杂性分析取整函数

x：不大于x的最大整数；

x：不小于x的最小整数。取整函数的若干性质x-1<xxx<x+1；

n/2+n/2=n;

对于n

0，a,b>0，有：

n/a/b=n/ab;

n/a/b=n/ab;

a/b(a+(b-1))/b;

a/b(a-(b-1))/b;其中，f(x)=x,g(x)=x

为单调递增函数。1.6 算法复杂性分析算法分析中常见的复杂性函数1.6 算法复杂性分析小规模数据复杂性增长图1.6 算法复杂性分析中等规模数据复杂性增长图小结程序与算法渐进表达式程序复杂性（1）选择语句：（1.1)if语句：（1.2)？语句：

if(expression)statement;elsestatement;exp1?exp2:exp3y=x>9?100:200;等价于：

if(x>9)y=100;elsey=200;（1.3)switch语句：switch(expression){case1:statementsequence;break;case2:statementsequence;break;

default:statementsequence;}（2）迭代语句：（2.1)for循环：

for(init;condition;inc)statement;（2.2)while循环：

while(condition)statement;（2.3)do-while循环：

do{statement;}while(condition);（3）跳转语句：（3.1)return语句：

returnexpression;（3.2)goto语句：

gotolabel;

label:（4）函数：例：

return-typefunctionname(para-list){bodyofthefunction}

intmax(intx,inty){returnx>y?x:y;}（5）模板template：template<classType>Typemax(Typex,Typey){returnx>y?x:y;}inti=max(1,2)；doublex=max(1.0,2.0)；（6）动态存储分配：（6.1）运算符new：