算法分析与设计-第01章-2009版.ppt

,南京邮电大学计算机学院5/21/2020,算法设计与分析,DesignandAnalysisofAlgorithmsInC+,主讲王海艳计算机学院wanghy,南京邮电大学计算机学院5/21/2020,教材：陈慧南.算法设计与分析-C+语言描述先修课：面向对象程序设计语言C+，数据结构性质：计算机科学与技术中处于核心地位的一门专业基础课。,南京邮电大学计算机学院5/21/2020,目的：通过学习掌握算法设计的主要方法，并对算法的时、空复杂性有正确分析的能力，能够针对具体的应用问题选择合适的数据结构和设计结构清晰、正确有效的算法，为独立设计算法和对算法进行复杂性分析奠定坚实的理论基础。基本任务:介绍算法的基本概念、算法设计的基本策略和方法，同时介绍算法复杂性的概念、性能分析的具体方法和技巧。教学重点:算法设计的基本思想和策略，以及算法性能分析的方法等。,南京邮电大学计算机学院5/21/2020,难点:如何将算法优化的思想贯穿在设计过程中，以及算法平均性能的分析技巧。总学时：48学时。成绩考核办法：平时成绩30%，期末考试70%。,南京邮电大学计算机学院5/21/2020,第1章算法问题求解基础,基本要求：本章概述算法问题、求解方法等重要概念和方法。掌握算法的基本概念，了解使用计算机求解问题的过程和方法。,南京邮电大学计算机学院5/21/2020,1.1算法概述1.2问题求解方法1.3算法设计与分析1.4递归和归纳,南京邮电大学计算机学院5/21/2020,1.1算法概述,南京邮电大学计算机学院5/21/2020,“计算机科学是一门研究算法的科学”计算机的运算速度很高，但是速度再高也有它的极限。为了充分发挥计算机的高速特点，应在计算机求解问题的过程中，尽量减少人工干预。为使计算机的计算过程能够解决某一特定问题，必须为计算机设定解决方案中的每个详细步骤，并将此过程完整的描述出来。算法Algorithm,南京邮电大学计算机学院5/21/2020,算法是数据结构的灵魂。不了解施加于数据上的算法就无法决定如何构造数据。反之，数据结构又是算法的基础。算法的结构和选择又常常在很大程度上依赖于数据结构。,算法+数据结构=程序,南京邮电大学计算机学院5/21/2020,1.1.1什么是算法,算法（algorithm）一个算法是对特定问题求解步骤的一种描述，它是指令的有限序列。,南京邮电大学计算机学院5/21/2020,输入(input)：算法有零个或多个输入量；输出(output)：算法至少产生一个输出量；确定性(definiteness)：算法的每一条指令都有确切的定义，没有二义性；能行性(effectiveness)：算法的每一条指令必须足够基本，它们可以通过已经实现的基本运算执行有限次来实现；有穷性(finiteness)：算法必须总能在执行有限步之后终止。,算法的五个特征:,南京邮电大学计算机学院5/21/2020,程序(Program)是算法用某种程序设计语言的具体实现。算法必须可终止，程序却没有这一限制。即：程序可以不满足算法的性质(5)“有穷性”。例如：操作系统是一个在无限循环中执行的程序，却不是算法。因此操作系统是使用计算机语言描述的一个计算过程，而不是一个算法。,南京邮电大学计算机学院5/21/2020,求最大公约数计算两个整数m和n(0mn)的最大公约数，记为gcd(m,n)。,南京邮电大学计算机学院5/21/2020,欧几里德算法(辗转相除法),gcd(24,60),=gcd(60mod24,24),=gcd(24mod12,12),=12,反复执行：gcd(m,n)=gcd(nmodm,m),直到：nmodm=0时的n,=gcd(12,24),=gcd(0,12),南京邮电大学计算机学院5/21/2020,【程序1-1】欧几里德递归算法intRGcd(intm,intn)if(m=0)returnn;returnRGcd(n%m,m);intGcd(intm,intn)if(mn)Swap(m,n);/保证mnreturnRGcd(m,n);,南京邮电大学计算机学院5/21/2020,【程序1-2】欧几里德迭代算法intGcd(intm,intn)if(m=0)returnn;if(n=0)returnm;if(mn)Swap(m,n);while(m0)intc=n%m;n=m;m=c;returnn;,gcd(m,n)=gcd(nmodm,m),南京邮电大学计算机学院5/21/2020,gcd的连续整数检测算法,最大公约数不会超过两数中的较小者，即不会超过t=minm,n(确定初值)执行while(m%t|n%t)t-;,gcd(9,27),gcd(4,6)如t=4,(4%4|6%4)0,t-t=3，(4%3|6%3)0,t-t=2,(4%2|6%2)=0,故最大公约数为2,南京邮电大学计算机学院5/21/2020,【程序1-3】Gcd的连续整数检测算法,1、一个问题可以设计不同的算法；如欧几里德，连续整数检测。,2、一个算法可以采用不同的形式；如递归，迭代。,intGcd(intm,intn)if(m=0)returnn;if(n=0)returnm;intt=mn?n:m;/t=minm,nwhile(m%t|n%t)t-;returnt;,南京邮电大学计算机学院5/21/2020,1.1.2为什么学习算法,是计算机科学的基础，更是程序的基石；只有具有良好的算法基础才能成为训练有素的软件人才。有来自不同计算领域的重要算法，也必须学会设计新的算法、确认其正确性并分析其效率。各个应用领域的研究和技术人员都在使用计算机求解各自专业领域的问题，他们需要设计算法，编写程序，开发应用软件。,南京邮电大学计算机学院5/21/2020,研究算法的重要性,假设某一负责人交给你一个很难的任务，几天后询问你问题解决了没有？可能会发生如下图这样的情况：,问：“交给你的问题，解决方案设计出来了吗？”答：“我找不到一个有效的算法来解决它，没能完成任务。”,南京邮电大学计算机学院5/21/2020,研究算法的重要性,问：“交给你的问题，解决方案设计出来了吗？”答：“我找不到一个有效的算法来解决它，因为这样的算法是不存在的。”,不过，要证明一个问题不存在有效算法，往往跟寻找有效算法一样难。,南京邮电大学计算机学院5/21/2020,研究算法的重要性,问：“交给你的问题，解决方案设计出来了吗？”答：“我找不到一个有效的算法来解决它，但不是我不行，因为所有这些名人也都找不到解决它的有效算法。”,如果是你的话，你愿意是哪种结果？,南京邮电大学计算机学院5/21/2020,1.2问题求解方法,南京邮电大学计算机学院5/21/2020,1.2.1问题和问题求解,问题求解（problemsolving）是寻找一种方法来实现目标。问题求解过程（problemsolvingprocess）是人们通过使用问题领域知识来理解和定义问题，并凭借自身的经验和知识去选择和使用适当的问题求解策略、技术和工具，将一个问题描述转换成问题解的过程。计算机求解问题的关键之一是寻找一种问题求解策略（problemsolvingstrategy），得到求解问题的算法，从而得到问题的解。,南京邮电大学计算机学院5/21/2020,1.2.2问题求解过程,理解问题（understandtheproblem）设计方案（deviseaplan）实现方案（carryouttheplan）回顾复查（lookback）,南京邮电大学计算机学院5/21/2020,1.2.3系统生命周期,一个计算机程序的开发过程就是使用计算机求解问题的过程。软件工程(softwareengineering)将软件开发和维护过程分成若干阶段，称为系统生命周期(systemlifecycle)或软件生命周期。,南京邮电大学计算机学院5/21/2020,软件生命周期划分为:分析（analysis）设计（design）编码（codingorprogramming）测试（testing）维护（maintenance）等5个阶段。前4个阶段属于开发期，最后一个阶段处于运行期。,南京邮电大学计算机学院5/21/2020,1.3算法设计与分析,南京邮电大学计算机学院5/21/2020,算法问题求解过程,理解问题,选择求解方法确定数据结构,设计算法,正确性证明,分析算法,编写代码,1.3.1算法问题求解过程,南京邮电大学计算机学院5/21/2020,算法分类一个精确算法(exactalgorithm)总能保证求得问题的解。一个启发式算法(heuristicalgorithm)通过使用某种规则、简化或智能猜测来减少问题求解时间。,南京邮电大学计算机学院5/21/2020,对于最优化问题，一个算法如果致力于寻找近似解而不是最优解，被称为近似算法（approximationalgorithm）。如果在算法中需做出某些随机选择，则称为随机算法（randomizedalgorithm）。,南京邮电大学计算机学院5/21/2020,1.3.2如何设计算法,使用计算机的问题求解策略主要指算法设计策略（algorithmdesignstrategy）。如果所求问题符合某种算法设计策略处理的问题特性，就可使用该算法设计策略设计算法、求解问题。,南京邮电大学计算机学院5/21/2020,1.3.3如何表示算法,算法描述方法自然语言流程图伪代码程序设计语言本书使用C/C+语言描述,南京邮电大学计算机学院5/21/2020,1.3.4如何确认算法,算法确认(algorithmvalidation):确认一个算法是否正确的活动。算法证明(algorithmproof):使用数学方法证明算法的正确性。程序测试(programtesting):是指对程序模块或程序总体，输入事先准备好的样本数据（称为测试用例，testcase），检查该程序的输出，来发现程序存在的错误及判定程序是否满足其设计要求的一项积极活动。,南京邮电大学计算机学院5/21/2020,1.3.5如何分析算法,算法分析（algorithmanalysis）:是指对算法的执行时间和所需空间的估算。程序的性能测量(performancemeasure-ment):在算法写成程序后，便可使用样本数据，实际测量一个程序所消耗的时间和空间。,南京邮电大学计算机学院5/21/2020,1.4递归和归纳,南京邮电大学计算机学院5/21/2020,1.4.1递归,递归定义递归（recursive）定义是一种直接或间接引用自身的定义方法。一个合法的递归定义包括两部分：基础情况（basecase）和递归部分。例1-1斐波那契数列,南京邮电大学计算机学院5/21/2020,例1-1斐波那契数列,南京邮电大学计算机学院5/21/2020,递归算法当一个算法采用递归方式定义时便成为递归算法。一个递归算法是指直接或间接调用自身的算法。【程序1-4】求FnlongFib(longn)if(n=1)returnn;elsereturnFib(n-2)+Fib(n-1);,南京邮电大学计算机学院5/21/2020,可以用所谓的递归树（recursivetree）来描述程序1-4的函数Fib执行时的调用关系。,图1-2计算Fib（4）的递归树,南京邮电大学计算机学院5/21/2020,递归数据结构使用递归方式定义的数据结构称为递归数据结构（recursivedatastructure）。,南京邮电大学计算机学院5/21/2020,1.4.2递归算法示例,例1-2逆序输出正整数的各位数【程序1-5】voidPrintDigit(unsignedintn)cout=10)PrintDigit(n/10);/以逆序输出前k-1位数,南京邮电大学计算机学院5/21/2020,例1-3汉诺塔问题（towerofHanoi）假定有三个塔座：X，Y，Z，在塔座X上有n个直径大小各不相同，按圆盘大小从小到大编号为1，2，n的圆盘。现要求将X塔座上n个圆盘移到塔座Y上，并仍按同样顺序叠排。圆盘移动时必须遵循下列规则：（1）每次只能移动一个圆盘；（2）圆盘可以加到塔座X，Y，Z中任意一个上；（3）任何时刻都不能将一个较大的圆盘放在较小的圆盘之上。,南京邮电大学计算机学院5/21/2020,南京邮电大学计算机学院5/21/2020,【程序1-6】汉诺塔问题enumtowerA=X,B=Y,C=Z;voidMove(intn,towerx,towery)/将第n个圆盘从塔座x移到塔座y的顶部coutThedisknismovedfromchar(x)totopoftowerchar(y)endl;,南京邮电大学计算机学院5/21/2020,voidHanoi(intn,towerx,towery,towerz)/将x上部的n个圆盘移到y上，顺序不变。if(n)Hanoi(n-1,x,z,y);Move(n,x,y);Hanoi(n-1,z,y,x);,南京邮电大学计算机学院5/21/2020,1.4.3归纳证明,定理1-1对于n0，程序1