第一讲算法基础

第一章算法及基础知识徐克奇xkq@教材

《算法设计与分析》王秋芬、吕聪颖等编著清华大学出版社2011年8月参考教材

1.《算法设计与分析》（第二版）王晓东编著清华大学出版社2008年1月

2.《算法设计与分析——c++语言描述》陈慧南编著电子工业出版社2006年5月《算法概论》(注释版).SanjoyDasgupta等著，钱枫等注释，机械工业出版社，2009《算法导论》（第二版影印版）．(美)Corrmen.T.H.北京：高等教育出版社，2002．5主要内容第1章 算法及基础知识第2章 贪心法第3章 分治法第4章 动态规划第5章 搜索法第6章 随机化算法第7章线性规划问题第8章数论算法及计算几何算法第9章NP完全理论为什么要学习算法？算法是计算机科学的基石。没有算法，计算机程序将不复存在学习算法可以提高人们的分析能力。算法可以看作是解决问题的一类特殊方法——它虽非问题的答案，但它是经过准确定义的，用来获得答案的过程。无论是否涉及计算机，特定的算法设计技术都能看作是问题求解的有效策略。算法的魅力：思考程序=算法+数据结构

算法让我们上一个更高的台阶一个皇室数学挑战问题(1202)假设兔子出生一个月后能繁殖，以后每月产一个孩子，一直下去直到永远。从一个兔子开始，问n个月后有多少个兔子？LeonardoFibonacci1170-1250兔子的繁殖成熟不成熟初始一个月二个月三个月四个月五个月兔子出生一个月后能繁殖，以后每月产一个孩子，一直下去……。设Fn是n个月时兔子的数量F1=1F2=1Fn=Fn-1+Fn-2Fibonaccinumbers:1,1,2,3,5,8,13,21,34,55,89,…数量增长非常快:F30>106!事实上,Fn≈20.694n

≈1.6n,指数级增长.可以证明(3/2)^n<Fn<(5/3)^n计算Fibonacci数functionFib1(n)ifn=1return1ifn=2return1returnFib1(n-1)+Fib1(n-2)一个递归算法关于算法我们总要问二个问题:它能正确工作吗?能–它直接实现了Fibonacci数的定义.它要花多长时间?这不是很明显的……运行时间分析functionFib1(n)ifn=1return1ifn=2return1returnFib1(n-1)+Fib1(n-2)设T(n)=计算F(n)的步数那么:T(n)>T(n-1)+T(n-2)但是Fn=Fn-1+Fn-2.因此T(n)>Fn指数级时间...这有多糟糕?例.计算F200大概需要2^140个运算.在一个快速计算机上要花多长时间?（在NECEarthSimulator上花2^92秒）指数级时间都那么糟糕吗?Earthsimulator计算机需要292秒计算F200.TimeinsecondsInterpretation21017分22012日23032年240山洞绘画作品

(一万五千年到一万七千年之间)245

直立人发现火251恐龙灭绝257地球形成260宇宙起源剖析为什么花这么长时间?让我们剖析该递归…functionFib1(n)ifn=1return1ifn=2return1returnFib1(n-1)+Fib1(n-2)同一个子问题被反复求解!好的算法很重要！学习算法要点:理解算法的概念。理解什么是程序，程序与算法的区别和内在联系。掌握算法的计算复杂性概念。掌握用C++/JAVA语言描述算法的方法。1.1 算法的基本概念算法（Algorithm）：即在有限步骤内解一个数学问题的过程，步骤中常常包括某一操作的重复。（韦氏词典）一个算法是解决一个问题或实现某一目标的逐步过程。（广义）算法是有穷规则的集合，规定了一个解决某一特定类型问题的运算序列。（D.E.Knuth唐纳德.E.克努特)输入性：有零个或多个外部量作为算法的输入。输出性：算法产生至少一个量作为输出。确定性：算法中每条指令清晰，无歧义。有穷性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。（计算过程，时效）可行性：算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质(4)即有穷性。如操作系统

算法是满足上述性质的指令序列。程序：1.1.1 算法的特征欧几里德算法mnr例：欧几里德算法——辗转相除法求两个自然数m和n的最大公约数①输入m

和n；②求m除以n的余数r；③若r等于0，则n为最大公约数，算法结束；否则执行第④步；④将n的值放在m中，将r的值放在n中；⑤重新执行第②步。欧几里德算法1.1.1 算法的4个标准正确性：在合理的数据输入下，能在有限的时间内得出正确的结果。可读性：应易于人的理解，易于调试。健壮性：具备检查错误和对错误进行适当处理的能力。效率：算法执行时所需计算机资源的多少，包括运行时间和存储空间。1.1.3算法的描述形式（1）自然语言优点：容易理解缺点：冗长、不够严谨、二义性使用方法：粗线条描述算法思想

注意事项：避免写成自然段（2）算法框图法

优点：流程图、盒图，流程直观、简洁、明了，便于理解和交流缺点：缺少严密性、灵活性使用方法：描述简单算法注意事项：注意抽象层次1.1.3算法的描述形式N开始输入m和nr=m%nr=0m=n；n=r输出n结束Y欧几里德算法（3）伪代码语言描述法伪代码（Pseudocode）：介于自然语言和程序设计语言之间的方法，它采用某一程序设计语言的基本语法，操作指令可以结合自然语言来设计。（算法语言）优点：表达能力强，抽象性强，容易理解1.1.3算法的描述形式

1.r=m%n;2.循环直到r等于02.1m=n;2.2n=r;2.3r=m%n;3.输出n;欧几里德算法（4）高级程序设计语言描述法优点：能由计算机执行缺点：抽象性差，对语言要求高使用方法：算法需要验证注意事项：将算法写成子函数1.1.3算法的描述形式#include<iostream.h>intCommonFactor(intm,intn){intr=m%n;while(r!=0){m=n;n=r;r=m%n;}returnn;}voidmain(){cout<<CommonFactor(63,54)<<endl;}欧几里德算法1.2算法设计的一般过程充分理解要解决的问题数学模型拟制---建立符合要求数学模型，设计相关约束条件算法详细设计---选择算法设计策略，确定数据结构算法描述---描述工具将算法具体过程描述下来算法思路的正确性验证算法分析---时间、空间复杂性算法的计算机实现和测试文档资料的编制算法设计的一般过程

1．理解问题2．预测所有可能的输入3.在精确解和近似解间做选择

4.确定适当的数据结构

5．算法设计技术6．描述算法

7．跟踪算法

8．分析算法的效率

9．根据算法编写代码

著名公式

Algorithm+DataStructure=Programming好的算法提高求解问题的效率节省存储空间需要解决的问题问题一个求解算法：算法设计技术算法算法的评价：

算法分析技术1.3算法分析算法复杂性=算法运行时所需要的计算机资源的量时间复杂性、空间复杂性影响时间复杂性的因素问题规模n、输入序列I、算法本身A影响空间复杂性的因素算法本身、输入输出数据、辅助变量算法复杂性的权衡时间复杂度和空间复杂度相互影响（时间换空间或空间换时间）1.3算法分析三种情况下的复杂性（结合顺序查找操作）最好情况Tmin（N)1次最坏情况Tmax（N)N次平均情况Tavg（N)(N+1)/2算法复杂性分析

当问题规模增大时，复杂度的极限行为称为算法的渐进时间复杂度。算法时间复杂度最大问题规模1秒1分1小时A1n10006*1043.6*106A2nlogn14048932.0*105A3N2312441897A4N31039153A52n91521算法时间复杂度加速前最大问题规模加速后最大问题规模A1nS110*S1A2nlognS2约为10*S2A3N2S33.16*S3A4N3S42.15*S4A52nS5S5+3.3假设下一代计算机的速度是目前的10倍，下表是计算机加速后在相同的时间内可以解决的问题规模增量。

算法渐近复杂性态设算法的运行时间为T(n)，如果存在T*(n)，使得

就称T*(n)为算法的渐进复杂性态或渐进时间复杂性。举例：假设算法A的运行时间表达式为T1(n)T1(n)=30n4+20n3+40n2+46n+100

假设算法B的运行时间表达式为T2(n)T2(n)=1000n3+50n2+78n+10随着n的增大，对算法的执行时间影响最大的是最高次方。算法A的运行时间可记为：T*1(n)≈n4算法B的运行时间可记为：T*2(n)≈n3渐近符号:O---上界---下界---精确界（上界和下界）渐进符号

1.大O符号(上界）定义1.1若存在两个正的常数c和n0，对于任意n≥n0，都有T(n)≤c×f(n)，则称T(n)=O(f(n))n0问题规模n执行次数n0之前的情况无关紧要T(n)c×f(n)f(N)是T(N)的一个上界，即T(N)的阶不高于f(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)O(Cf(N))=O(f(N))，其中C是一个正的常数；

(5)f=O(f)2.大Ω符号（下界）定义1.2若存在两个正的常数c和n0，对于任意n≥n0，都有T(n)≥c×g(n)，则称T(n)=Ω(g(n))n0问题规模n执行次数n0之前的情况无关紧要T(n)c×g(n)渐进符号（续）

g(N)是T(N)的一个下界，即T(N)的阶不低于g(N)的阶3.Θ符号（同阶）定义1.3若存在三个正的常数c1、c2和n0，对于任意n≥n0都有c1×f(n)≥T(n)≥c2×f(n)，则称T(n)=Θ(f(n))

n0问题规模n执行次数n0之前的情况无关紧要T(n)c2×f(n)c1×f(n)渐进符号（续）

当且仅当f(N)=O(g(N))且f(N)=Ω(g(N))。称f(N)与g(N)同阶。例:

求T(n)=10n+4的渐进上界O(n)算法分析中常见的复杂性函数几种常见的时间复杂度函数按数量级从小到大的顺序依次是：Θ(1),Θ(logn)，Θ(sqrt(n))，Θ(n)，Θ(nlogn)，Θ(n2)，Θ(n3)，Θ(2n)，Θ(n!)在多项式中，n的最高次指数是最主要的决定因素，常数项、低次幂项和系数都是次要的。例：求T(n)=amnm+am-1nm-1+…+a1n+a0的上界、下界根据定理1T(n)=Θ(nm)时间复杂度分析的基本规则主要考虑可执行语句的情况：输入、输出、赋值语句，为O（1）；顺序结构，采用渐进式O的求和规则来进行计算；选择结构，考虑判定后所执行语句的执行时间O（max(T(s1),T(s2))）；循环结构，考虑循环判定条件和循环体语句的执行时间，采用渐进式O的乘积规则来进行计算；复杂算法，先分割，然后采用渐进式O的求和规则和乘法规则来计算整个算法的时间复杂度；基本语句—对算法运行时间贡献最大的原操作语句。当算法时间复杂性只依赖于问题规模时，选择基本语句执行次数来作为运行时间T(n)建立的依据。例：求数组中元素最大值空间复杂度算法所占用的存储空间包括算法自身输入、输出辅助空间空间复杂度S(n)=O(f(n))，以最坏情况来分析例：插入法升序排序voidinsert_sort(intn,ints[]){inta,i,j;for(i=1;i<n;i++){a=s[i];j=i-1;while(j>=0;&&s[j]>a){s[j+1]=s[j];j--;}s[j+1]=a;}}1.4递归（是算法设计与描述的有力工具）子程序（或函数）直接调用自己或通过一系列调用语句间接调用自已，称为递归。直接或间接调用自身的算法称为递归算法。采用递归算法来求解问题的一般步骤：分析问题，寻找递归关系找出停止条件构建函数体n的阶乘停止条件递归关系停止条件与递归关系是递归函数的两个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。Longlongfun(intn){if(n<0){printf(“illegalnumber!\n”);break;}elseif(n==0)return1;elsereturnn*fun(n-1);}例：排列问题问题描述n个元素，它们的编号为1,2,…,n，排列问题的目的是生成这n个元素的全排列。解题步骤分析递归关系找出停止条件设计递归函数算法设计思路将规模为n的排列问题转化为规模为n-1的排列问题。将规模为n-1的排列问题转化为规模为n-2的排列问题将问题规模一级一级降至1，1个元素的排列是它本身，此时到达递推的停止条件。数组中的元素即为1个排列，然后进行回归依次得到其它的排列。共要递归K次（K=n，n-1,n-2，…，1)当k=1输出一个排列如何将规模为n的排列问题转化为规模为n-1的排列问题。步骤1：数组的首元素为第一个元素，还需生成后面n-1个元素全排列。步骤2：将数组的第一个元素和第二个元素交换，数组的首元素为第二个元素，还需生成后面n-1个元素全排列。步骤3：将数组的第一个元素和第三个元素交换，数组的首元素为第三个元素，还需生成后面n-1个元素全排列。步骤4：…步骤n:数据结构：

intA[n]-----按次序存放1~n个数排列算法voidperm(inta[],intk,intn)

{if(k==1){

输出一个排列}else

for(i=n-k;i<n;i++)

{

swap(a[n-k],a[i]);

perm(a,k-1,

n);

swap(a[n-k],a[i]);}}时间复杂度：采用后向代入法计算可得到通项公式： T(n)=nT(n-1) =n(n-1)T(n-2)=……

=n(n-1)(n-2)......2T(1) =n!

时间复杂度：O(n!)递归算法的空间复杂度：算法的递归深度全排列算法perm共执行了n次递归深度为n空间复杂度(递归)：O(n)回到Fibonacci数列问题functionFib1(n)ifn=1return1ifn=2return1returnFib1(n-1)+Fib1(n-2)同一个子问题被反复求解!Fibonacci数列一个较好的算法子问题:F1,F2,…,Fn.依次求解它们并保存它们的值!functionFib2(n)Createanarrayfib[1..n]fib[1]=1fib[2]=1fori=3ton:fib[i]=fib[i-1]+fib[i-2]returnfib[n][1]它返回正确的答案吗？[2]它有多快?运算数与n成比例.[以前的方法:20.7n]F200现在可在合理时间内计算出来,F2000和F20000也一样.启示

:恰当的算法使事情彻底改观

。第三个算法用矩阵重写F0=0,F1=1,Fn=Fn-1+Fn-2如下:因此只需快速计算多项式级vs.指数级运行时间如n,n2,n3是多项式级。运行时间如2n,en,2n是指数级.多项式是适当的指数级是不适当的在算法分析中，这是最基本的一个分界线.1.5基本数据结构顺序表——链表连续存储——离散存储定位、插入、删除栈——队列FILO——FIFOTop、bottom——Front、Rear树概念基本术语结点的度:树的度:叶子结点:分支结点:分支的个数树中所有结点的度的最大值度为零的结点度大于零的结点DHIJM孩子结点、双亲结点、兄弟结点、堂兄弟祖先结点、子孙结点结点的层次:树的深度：ABCDEFGHIJMKL假设根结点的层次为1,它的孩子结点为第二层，依此类推一个结点所在的层次，为其双亲结点所在的层次加1。树中叶子结点所在的最大层次任何一棵非空树是一个二元组

Tree=（root，F）其中：root被称为根结点，

F被称为子树森林森林：是m（m≥0）棵互不相交的树的集合ArootBEFKLCGDHIJMF树的存储结构双亲存储结构typedefstruct{ElemTypedata;intparent;}Ptree[MaxSize];链存储结构typedefstructnode{ElemTypedata;structnode*sons[MaxSons];}TSonNode;图定义

图(Graph)G由两个集合V(Vertex)和E(Edge)组成,记为G=(V,E),其中V是顶点的有限集合,记为V(G),E是连接V中两个不同顶点(顶点对)的边的有限集合,记为E(G)。EACBDBCAFED图的基本术语邻接点相关边路径