第一章-算法的基本概念

课时数：32学时上课：1-13周成绩：期末成绩（60%）+平时成绩（40%）教材：算法设计与分析（第3版），王晓东，清华大学出版社参考书：(1)算法设计与分析（第二版）,郑宗汉，清华大学出版社(2)算法导论，ThomasH.Cormen编著.潘金贵等译，机械工业出版社,算法分析与设计,课程主要内容,算法引论递归与分治贪心算法动态规划法回溯法分支限界法,课程主要内容,算法理论的两大论题：1、算法设计面对一个问题，如何设计一个有效的算法2、算法分析对已设计的算法如何评价或判断其优劣,算法的基本概念,第一章,1.1引言,1.2算法的时间复杂性,1.3算法的时间复杂性分析,1.4算法的空间复杂性,1.5最优算法,1.1引言,1202年，意大利数学家Fibonacci出版了他的算盘全书。他在书中提出了一个关于兔子繁殖的问题：假设兔子出生一个月后能繁殖，以后每月产一个孩子，一直下去直到永远。从一个兔子开始，问n个月后有多少个兔子？,一个古老经典的数学问题,LeonardoFibonacci1170-1250,1.1引言,兔子出生一个月后能繁殖，以后每月产一个孩子，一直下去。,设Fn是n个月时兔子的数量,F1=1F2=1Fn=Fn-1+Fn-2,Fibonaccinumbers:1,1,2,3,5,8,13,21,34,55,89,数量增长非常快:F30接近106事实上,Fn20.694n1.6n,指数级增长。,1.1引言,计算F200大概需要2140个运算。在一个快速计算机上要花多长时间?（在NECEarthSimulator上花292秒）,EarthSimulator,TimeinsecondsInterpretation21017分22012日23032年240山洞绘画作品(一万五千年到一万七千年之间)245直立人发现火251恐龙灭绝257地球形成260宇宙起源,1.1引言,好的算法很重要！,1.1.1算法的由来,中文名称：周髀算经英文名称“Algorithm”来源于9世纪波斯数学家花拉子米（al-Khwarizmi）“算法”原为“algorism”，即“al-Khwarizmi”的音转，意思是“花拉子米”的运算法则在18世纪演变为“algorithm”,世界上最早的算法是哪个国家提出来的？A.中国B.希腊C.阿拉伯D.埃及,最早的算法欧几里德的“求最大公因子算法”,1.1.2为什么要学习算法,70年代前计算机科学的主题没有被清楚得认清70年代Knuth出版了TheArtofComputerProgramming以算法研究为主线确立了算法为计算机科学基础的重要主题1974年获得图灵奖70年代后算法作为计算机科学核心推动了计算机科学技术飞速发展,1.1.2为什么要学习算法,算法是计算机科学的基石。没有算法，计算机程序将不复存在学习算法可以提高人们的分析能力。算法可以看作是解决问题的一类特殊方法它虽非问题的答案，但它是经过准确定义的，用来获得答案的过程。无论是否涉及计算机，特定的算法设计技术都能看作是问题求解的有效策略。,1.1.2为什么要学习算法,什么是程序？与算法是什么关系？程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的有限性。例如，操作系统是一个在无限循环中执行的程序，因而不是一个算法。操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现，该子程序得到输出结果后便终止。,1.1.2为什么要学习算法,算法研究的核心问题是时间（速度）问题。计算机功能越强大，人们就越想去尝试更复杂的问题，而更复杂的问题需要更大的计算量。现代计算技术在计算能力和存储容量上的革命仅仅提供了计算更复杂问题的有效工具，无论硬件性能如何提高，算法研究始终是推动计算机技术发展的关键。,1.1.2为什么要学习算法,基因工程人类基因项目的目标是找出人类DNA中的所有100000种基因，确定构成人类DNA的30亿种化学基对的各种序列，将这些信息存储在数据库中，并开发出用于进行这方面数据分析的工具。这些步骤中的每一个都需要复杂的算法。,1.1.2为什么要学习算法,检索技术因特网是的全世界的人们都能够快速地访问和检索大量的信息。为了能实现这一目的，人们才用了巧妙的算法来管理和操纵大量的数据。这方面必须解决的问题包括寻找好的数据传输路径、利用搜索引擎来快速地找到包含特定信息的网页等。,1.1.2为什么要学习算法,信息安全与数据加密电子商务使得商品和服务可以以垫子的形式进行谈判和交易。然而，电子商务想要得到广泛应用的话，非常重要的一点就是保持信用卡号、密码、银行结单等信息的私密性。公共密钥加密技术和数字签名技术是这一领域内所使用的核心技术，他们的基础就是数值算法和数论理论。,1.1.3算法及其重要特性,算法的定义算法是解某一特定问题的一组有穷规则的集合。算法设计的先驱者唐纳德.E.克努特（DonaldE.Knuth）对算法的特性作了如下的描述：算法的五个重要特性：有限性、确定性、输入、输出、能行性,1.1.3算法及其重要特性,1、有限性。算法在执行有限步之后必须终止。2、确定性。算法的每一个步骤，都有精确的定义。要执行的每一个动作都是清晰的、无歧义的。例：不符合确定性的运算5/0将6或7与x相加未赋值变量参与运算,1.1.3算法及其重要特性,3、输入。一个算法有0个或多个输入，它是由外部提供的，作为算法开始执行前的初始值，或初始状态。4、输出。一个算法有一个或多个输出，这些输出，和输入有特定的关系，实际上是输入的某种函数。,1.1.3算法及其重要特性,5、能行性。算法的能行性指的是算法中有待实现的运算，都是基本的运算。原则上可以由人们用纸和笔，在有限的时间里精确地完成。实际应用中，时间花费可接受。,1.1.3算法及其重要特性,欧几里德曾在他的著作中描述过求两个数的最大公因子的过程。20世纪50年代，欧几里德所描述的这个过程，被称为欧几里德算法。例：欧几里德算法辗转相除法求两个自然数m和n的最大公约数,1.1.4算法的描述方法,自然语言优点：容易理解缺点：冗长、二义性注意：避免写成自然段,欧几里德算法,输入m和n；求m除以n的余数r；若r等于0，则n为最大公约数，算法结束；否则执行第步；将n的值放在m中，将r的值放在n中；重新执行第步。,1.1.4算法的描述方法,流程图优点：流程直观缺点：缺少严密性、灵活性使用方法：描述简单算法,起止框,处理框,判断框,输入输出框,流程线,1.1.4算法的描述方法,(3)程序设计语言优点：能由计算机执行缺点：抽象性差，对语言要求高,inteuclid(intm,intn)intr;r=m%n;while(r!=0)m=n;n=r;r=m%n;returnn;intmain()cout最大公约数为：euclid(66,12);return0;,1.1.4算法的描述方法,(4)伪代码（Pseudocode）介于自然语言和程序设计语言之间的方法，它采用某一程序设计语言的基本语法，操作指令可以结合自然语言来设计。优点：表达能力强，抽象性强，容易理解,1.r=m%n;2.循环直到r等于02.1m=n;2.2n=r;2.3r=m%n;3.输出n;,1.1.5算法设计的过程,问题分析：准确、完整地理解和描述问题是解决问题的第一步。建立数学模型：用计算机解决实际问题必须有合适的数学模型。算法设计与选择：算法设计是指设计求解某一特定类型问题的一系列步骤，并且这些步骤是可以通过计算机的基本操作来实现的。算法设计要同时结合数据结构的设计，简单说，数据结构的设计就是选取存储方式。算法分析：算法分析的目的，首先为了对算法的某些特定输入，估算该算法所需的内存空间和运行时间；其次是为了建立衡量算法优劣的标准，用以比较同一类问题的不同算法。通常将时间和空间的增长率作为衡量的标准。,1.1.5算法设计的过程,算法实现：根据选用的程序设计语言，要解决下列一些问题：有哪些变量，它们是什么类型？需要多少数组，规模有多大？用什么结构来组织数据？需要哪些子算法？等等。算法的实现方式，对运算速度和所需内存容量都有很大影响。程序调试：算法测试的实质是对算法应完成任务的实验证实，同时确定算法的使用范围。测试方法一般有两种：白盒测试对算法的各个分支进行测试；黑盒测试检验对给定的输入是否有指定输出。,1.1.5算法设计的过程,编制整理文档：编制文档的目的是让人了解你编写的算法。首先要把代码编写清楚。代码本身就是文档。同时还要采用注释的方式。另外还包括算法的流程图，自顶向下各研制阶段的有关记录，算法的正确性证明（或论述），算法测试结果，对输入/输出的要求及格式的详细描述等。,在以上步骤中，算法设计是解决问题的核心。,1.1.6算法设计的例子穷举法,例1.1百鸡问题。公元5世纪末，我国古代数学家张丘建在他所撰写的算经中提出了这样一个问题：鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一。百钱买百鸡，问鸡翁、母、雏各几何？,1.1.6算法设计的例子穷举法,例1.1百鸡问题。a：公鸡只数，b：母鸡只数，c：小鸡只数。约束方程：a+b+c=100（1.1.1）5a+3b+c/3=100（1.1.2）c%3=0（1.1.3）第一种解法：a、b、c的可能取值范围：0100，对在此范围内的，a、b、c的所有组合进行测试，凡是满足上述三个约束方程的组合，都是问题的解。,1.1.6算法设计的例子穷举法,例1.1百鸡问题。把问题转化为n元钱买n只鸡，n为任意正整数，则方程（1.1.1）、（1.1.2）变成：a+b+c=n（1.1.4）5a+3b+c/3=n（1.1.5）,算法1.2百鸡问题输入：所购买的三种鸡的总数目n输出：满足问题的解的数目k,公鸡,母鸡,小鸡的只数g,m,s1.voidchicken_question(intn,int13.14.15.16.17.,执行时间：外循环：n+1次中间循环：（n+1）*（n+1）次内循环：（n+1）*（n+1）*（n+1）次当n=100时，内循环的循环体执行次数大于100万次。,1.1.6算法设计的例子穷举法,例1.1百鸡问题。第二种解法：公鸡只数：0n/5母鸡只数：0n/3小鸡只数：n-a-b,执行时间：外循环：n/5+1次内循环：（n/5+1）*（n/3+1）次当n=100时，内循环的循环体执行次数为21*34=714次。,算法1.3改进的百鸡问题输入：所购买的三种鸡的总数目n输出：满足问题的解的数目k,公鸡,母鸡,小鸡的只数g,m,s1.voidchicken_problem(intn,int15.16.17.18.,1.1.6算法设计的例子穷举法,例1.2货郎担问题。某售货员要到若干个城市销售货物，已知各城市之间的距离，要求售货员选择出发的城市及旅行路线，使每一个城市仅经过一次，最后回到原出发城市，而总路程最短。,实际中有很多问题可以归结为这类问题。,1.1.6算法设计的例子穷举法,实际中很多问题都可以归结为货郎担这类问题。如：物资运输路线中，汽车应该走怎样的路线使路程最短；工厂里在钢板上要挖一些小圆孔，自动焊接机的割咀应走怎样的路线使路程最短；城市里有一些地方铺设管道时，管子应走怎样的路线才能使管子耗费最少，等等。,1.1.6算法设计的例子穷举法,Dijkstra提出了一个按路径长度递增的顺序逐步产生最短路径的方法，称为Dijkstra算法。,1.1.6算法设计的例子穷举法,例1.2货郎担问题。三个城市：有2!个“遍历”路径，每个路径需做2次加法，一次比较运算。共有32！运算。,1.1.6算法设计的例子穷举法,例1.2货郎担问题。四个城市，有3!个“遍历”路径，每个路径需做3次加法，一次比较运算。共有43！运算。,1.1.6算法设计的例子穷举法,例1.2货郎担问题。n个城市，有（n-1）!个“遍历”路径，每个路径需做(n-1)次加法，一次比较运算。共有n(n-1)！=n!运算。,1.1.6算法设计的例子穷举法,例1.2货郎担问题。假定while循环体执行一次需要1us的时间,对某类特定问题，穷举法只适用于规模较小的情况。,1.1.6算法设计的例子穷举法,好的算法很重要！,1.1.7算法的复杂性分析,用算法的复杂性来衡量算法的效率。算法的时间复杂性和算法的空间复杂性。算法的时间复杂性越高，算法的执行时间越长；反之，执行时间越短。算法的空间复杂性越高，算法所需的存储空间越多；反之越少。时间复杂性T(n)：算法的执行时间空间复杂性S(n)：算法所需的存储空间算法设计目标：时间复杂性、空间复杂性低,1.2算法的时间复杂性,算法的执行时间随问题规模的增大而增大，故常用关于问题规模n的函数估算算法在大规模问题时的运行时间。一、算法复杂性的度量？二、如何分析和计算算法的复杂性？,1.2.1算法的输入规模和运行时间的阶,先假设百鸡问题的两个算法，其最内部的循环体每执行一次，需1s时间。n=100第一个算法，循环次数100万次，时间1s第二个算法，循环次数714次，时间714sn=10000第一个算法，循环次数100003次，时间11天零13小时第二个算法，循环次数（10000/5+1）*（10000/3+1）次，时间6.7秒,1.2.1算法的输入规模和运行时间的阶,程序时间的增长速度随算法的不同而不同没有一个方法能够准确地计算算法的具体执行时间算法的具体执行时间不但取决于算法实现，也取决于算法用什么语言实现，用什么编译系统实现，在什么样的计算机上执行。即使在同一台计算机上，加法和乘法的执行时间差别也很大实际上在评估一个算法时，并不需要对算法的时间作出准确统计。对两个算法性能进行比较时，只需要相对时间人们更关心算法的运行时间随着输入规模的增长而增长的情况,1.2算法的时间复杂性,运行时间T(n)的估算可以假定算法是在这样的计算模型下运行的：所有操作数都具有相同的固定字长；所有操作的时间花费都是一个常数时间间隔。这样的操作叫做初等操作，如：算术运算；比较和逻辑运算；赋值运算，等等；,1.2算法的时间复杂性,voidchilden_question(intn,int/4(n+1)3,例：输入规模为n，百鸡问题的第一个算法的时间花费，可估计如下：,1.2算法的时间复杂性,运行时间T(n)的估算当n增大时，算法1.1的执行时间取决于式(1.1)的第一项可写成：阶是n3。,1.2算法的时间复杂性,运行时间T(n)的估算百鸡问题的第二个算法的时间花费：当n很大，可写成,1.2算法的时间复杂性,算法的渐进时间复杂性T*(n)定义1.2设算法的执行时间T(n)，如果存在，使得：,就称为算法的渐近时间复杂性。,在算法分析中，往往对算法的时间复杂性和算法的渐进时间复杂性不加区分。,在数学上，T(n)与T*(n)有相同的最高阶项，可取T*(n)为略去T(n)的低阶项后剩余的主项。当n充分大时，用T*(n)代替T(n)作为算法复杂性的度量，从而简化分析。,1.2算法的时间复杂性,算法的渐进时间复杂性T*(n)举例：假设算法A的运行时间表达式为：T1(n)=30n4+20n3+40n2+46n+100假设算法B的运行时间表达式为T2(n)：T2(n)=1000n3+50n2+78n+10随着n的增大，对算法的执行时间影响最大的是最高次方。算法A的运行时间可记为：T1*(n)n4算法B的运行时间可记为：T2*(n)n3,1.2算法的时间复杂性,运行时间的阶常用的时间复杂度的阶有：logn（对数阶）、n（线性阶）、nlogn（线性对数阶）、n2（平方接）、n3（立方接）、2n（指数阶）当n足够大时：lognnnlognn2n32n,1.2算法的时间复杂性,表1.2不同时间复杂性下不同输入规模的运行时间（假定每一个操作是1ns）,1.2算法的时间复杂性,渐进时间复杂性举例假设A1,A2,A6是求同一问题的6个算法，其时间复杂性分别为n、nlogn、n2、n3、2n、n!，并假设在计算机C1和C2上运行，C2机的速度是C1机的10倍。若这些算法在C1和C2机上的运行时间均为T，各算法在C1和C2机上可处理规模n1和n2的关系。,1.2算法的时间复杂性,渐进时间复杂性举例,可见，当计算机速度提高10倍后，算法A1的求解规模可扩大10倍，而算法A5只有微小增加，A6基本不变。时间复杂性为2n或n！这类算法，用提高计算机的速度来扩大它们的求解规模，其可能性是微乎其微的。,表1.3计算机速度提高10倍后，不同算法复杂性求解规模的扩大情况,1.2算法的时间复杂性,渐进时间复杂性举例,多项式时间算法：计算机速度的提高，可使解题规模以一个常数因子的倍数增加。（A1A4）指数时间算法：计算机速度的提高，不能扩大求解规模。（A5、A6）,1.2算法的时间复杂性,渐进时间复杂性举例,假设两个算法的输入规模都是n，判断以下两个算法A和B哪个更好？算法A要做2n+3次操作（先执行n次的循环，执行完成后再有一个n次的循环，最后有3次运算）算法B要做3n+1次操作。,1.2算法的时间复杂性,渐进时间复杂性举例,1.2算法的时间复杂性,渐进时间复杂性举例,1.2算法的时间复杂性,渐进时间复杂性举例,算法C是4n+8，算法D是2n2+1。,1.2算法的时间复杂性,渐进时间复杂性举例,1.2算法的时间复杂性,渐进时间复杂性举例,算法E是2n2+3n+1，算法F是2n3+3n+1,1.2算法的时间复杂性,渐进时间复杂性举例,1.2算法的时间复杂性,渐进时间复杂性举例,算法G是2n2，算法H是3n+1，算法I是2n2+3n+1,1.2算法的时间复杂性,渐进时间复杂性举例,1.2算法的时间复杂性,渐进时间复杂性举例,1.2算法的时间复杂性,算法运行时间主要取决于问题的规模，对于足够大的输入，算法运行时间表达式里的那些低阶项以及高阶项的常数系数等，主要受高阶项的制约。为了表示算法的渐进有效性，引入渐进符号以便表示算法的运行时间与输入规模之间的主要关系，即渐进时间复杂性，来衡量算法的好坏。当我们进行算法分析时，可以利用数学符合对算法的复杂性进行描述，这些数学符合是O表示法、表示法和表示法。这些表示法可以方便地表示算法的计算复杂度(computationalcomplexity)。,1.2算法的时间复杂性,运行时间的上界，O记号,f(n)=O(g(n)当且仅当存在正的常数c和n0，使得对于所有的nn0，有f(n)cg(n)。此时，称g(n)是f(n)的一个上界。,O(g(n)=f(n):存在正常数c和n0，对于任意nn0，有0f(n)cg(n)。,O(g(n)是一个集合，记f(n)=O(g(n),1.2算法的时间复杂性,运行时间的上界，O记号,定理：如果存在，且,则必有f(n)=O(g(n)。含义：f(n)的增长最多象g(n)的增长那样快，或f(n)的阶不高于g(n)的阶。称O(g(n)是f(n)的上界。,1.2算法的时间复杂性,3n=O(n)存在c=4，当n1时，有3n4n，所以3n=O(n)；2n2+11n-10=O(n2)存在c=3，当n10时有2n2+11n-101n2，所以有2n2+11n-10=O(n2)n2=O(n3)存在c=1，当n10时有n21n3，所以有n2=O(n3),1.2算法的时间复杂性,例：百鸡问题的第二个算法：取n0=28，对nn0，有：令，并令，有：,1.2算法的时间复杂性,例：百鸡问题的第二个算法：,方法二：,1.2算法的时间复杂性,O记号常用来分析算法的复杂性：,O记号表示上界，通常用来表示算法最坏情况下运行时间的上界，这是对任意输入来说的。比如，对于插入排序，对于任意输入情况，包括杂乱无序的情况，其运运行时间的上界是O(n2)。但对于已经排好序的这种特例，运行时间为O(n)。,1.2算法的时间复杂性,运行时间的下界，记号,f(n)=(g(n)当且仅当存在正的常数c和n0，使得对于所有的nn0，有f(n)c(g(n)。此时，称g(n)是f(n)的一个下界。,(g(n)=f(n):存在正常数c和n0，对于任意nn0，有0cg(n)f(n)。,(g(n)是一个集合，记f(n)=(g(n),1.2算法的时间复杂性,运行时间的下界，记号,定理：如果存在，且,则必有f(n)=(g(n)。含义：f(n)的增长至少象g(n)的增长那样快，或f(n)的阶不低于g(n)的阶。表示解一个特定问题的任何算法的时间下界。,1.2算法的时间复杂性,运行时间的下界，记号,例：n=(n1/2)因为存在c=1,n1时，使得1n1/2n作用：记号表示下界，通常用来表示算法最好情况下运行时间的下界，这是对任意输入来说的。,1.2算法的时间复杂性,运行时间的下界，记号,百鸡问题的第二个算法第11、12、13、14行，仅在条件成立时才执行，其执行次数未知。假定条件都不成立，这些语句一次也没有执行，该算法的执行时间至少为：,1.2算法的时间复杂性,运行时间的下界，记号,方法一：,方法二：,1.2算法的时间复杂性,运行时间的准确界，记号,百鸡问题的第二个算法，运行时间的上界是13n2，下界是n2，这表明不管输入规模如何变化，该算法的运行时间都界于13n2和n2之间。这时，用记号来表示这种情况，认为这个算法的运行时间是(n2)。记号表明算法的运行时间有一个较准确的界。,1.2算法的时间复杂性,运行时间的准确界，记号,f(n)=(g(n)当且仅当存在正的常数c1、c2和n0，使得对于所有的nn0，有0c1g(n)f(n)c2g(n)。此时，称(n)是f(n)的一个确界。,(g(n)=f(n):存在正常数c1、c2和n0，对于任意nn0，有0c1g(n)f(n)c2g(n)。,(g(n)是一个集合，记f(n)=(g(n),1.2算法的时间复杂性,运行时间的准确界，记号,定理：如果存在，且,则必有f(n)=(g(n)。含义：f(n)与g(n)同阶,1.2算法的时间复杂性,例：要使得对于所有nn0，有成立，可以选择c1=1/14，c2=1/2以及n0=7。当然c1，c2还存在其他选择。,是一个集合，除了，还有：,1.2算法的时间复杂性,例：常函数f(n)=4096。令n0=0，c=4096，使得对g(n)=1，对所有的n有：f(n)4096*1=cg(n)f(n)=O(g(n)=O(1)f(n)4096*1=cg(n)f(n)=(g(n)=(1)cg(n)f(n)cg(n)f(n)=(1)。,1.2算法的时间复杂性,例：线性函数f(n)=5n+2。令n0=0，当nn0时，有c1=5，g(n)=n，使得：f(n)5n=c1g(n)f(n)=(g(n)=(n)。令n0=2，当nn0时，有c2=6，g(n)=n：f(n)5n+n=6n=c2g(n)f(n)=O(g(n)=O(n)。同时，有：c1g(n)f(n)c2g(n)f(n)=(n),1.2算法的时间复杂性,例：平方函数f(n)=8n2+3n+2。令n0=0，当nn0时，有c1=8，g(n)=n2，使得：f(n)8n2=c1g(n)f(n)=(g(n)=(n2)。令n0=2，当nn0时，有c2=12,g(n)=n2：f(n)8n2+3n+n12n2=c2g(n)f(n)=O(g(n)=O(n2)同时，有：c1g(n)f(n)c2g(n)f(n)=(n2),1.2算法的时间复杂性,结论令：f(n)=aknk+ak-1nk-1+a1n+a0则有：f(n)=O(nk)，且f(n)=(nk)，因此，有