1 算法概述2013

算法设计与分析算法是什么?算法有什么用?算法设计与分析在计算机科学与技术学科中地位。程序=算法+数据结构什么是算法？一个算法是定义良好的计算过程，需要设置输入一些值，作为输入，并生成一些值作为输出。因此一个算法是计算步骤序列，将输入转换成输出。CopyrightLiZimao@2007-2008-1SCUEC为什么要学习算法这门课程？DonaldE.Knuthstated“ComputerScienceisthestudyofalgorithms”Cornerstoneofcomputerscience.Programswillnotexistwithoutalgorithms.算法和我们的生活密切相关有利于引导他人如何分析问题和解决问题有利于提高通过计算机解决问题的能力各项任务、各类问题都以算法为基础计算机可以更快，但是有限的。内存可更便宜，但仍然是有代价的。时间和空间资源应该使用得当，算法应该是有效的。学生应该做到：了解课程知识结构理解各类典型问题的算法和和各类方法的算法例程初步具备设计和实现算法的能力学习用数学方法分析算法。先导知识：有一些编程经验。特别是应该理解递归程序数组、链表、数等数据结构知识。有数学归纳法的基础。教材和主要参考书1．王晓东编著《算法分析与设计》清华大学出版社~xujia/mirror/algorithm.myrice.com/2.麻省理工学院IntroductiontoAlgorithms,SecondEditionCopyrightLiZimao@2007-2008-1SCUECGradingSchemesTotal100上课到课和作业:15%实验及设计报告:15%期中考试:70%第一讲算法概述理解算法的基本特性算法的表示算法的计算复杂性分析入门1.1算法的定义算法可以理解为由基本运算及规定的运算顺序所构成的完整的解题步骤。按照要求设计好的有限的确切的计算序列，并且这样的步骤和序列可以解决一类问题。Analgorithmisastep-by-stepprocedureforsolvingaprobleminafinitenumberofsteps.算法是任何定义好了的计算程式，它取某些值或值的集合作为输入，并产生某些值或值的集合作为输出。因此，算法是将输入转化为输出的一系列计算步骤。算法是若干指令的有穷序列，满足性质：(1)输入：必须明确指定有效的输入。(2)输出：可以证明对于给定的有效输入，产生正确的输出。(3)确定性：组成算法的每条指令是清晰，无歧义的。(4)有效性：每步运算必须足够简单和基本。(5)有穷性：一个算法必须保证执行有限步之后结束算法的正确性对于每一个输入实例，算法停止于正确的输出，则这个算法是正确的，即正确的算法解决了给定的计算问题。例，从A[1:n]中找最大数。1.输入n个数到数组A2.max=A[1]3.fori=2tondoifA[i]maxthenmax=A[i]4.输出max不正确的算法在一些输入实例不会有正确的输出。算法的有效性1.输入n个数到数组A2.max=A[1]3.fori=2tondoifA[i]maxthenmax=A[i]4.输出max第一步不是一条简单命令，但可以转换成多条简单语句如果修改一下：1.存在n个数1.2算法的表示1、自然语言2、流程图3、伪代码程序（或算法语言程序）3、判定树1.2.1自然语言例：有一个牧羊人带着一头羊,一只狼和一颗大白菜准备用一只很小的船过河。牧羊人每次只能带一样东西过去,可是如果让狼与羊单独在一起,狼会吃羊,让羊与白菜单独在一起,羊会吃白菜，设计牧羊人过河的流程。过河流程如下：1、人和羊过河，人返回，留下羊2、人和狼过河，人和羊返回，留下狼3、人和菜过河，人返回，留下菜4、人和羊过河1.2.2流程图冒泡如排序算法流程图开始输入A初始化i≤n？yesjn？A[j]A[j+1]?noyes交换A[j]A[j+1]?交换A[j]A[j+1]?j←j+1i←i+1结束输出Anoyes1.2.3伪代码用介于自然语言和计算机语言之间的文字和符号（包括数学符号）来描述算法伪代码与C、Java很相似。冒泡如排序算法的核心流程：fori←1ton-1doforj←1ton-idoifa[j]a[j+1]then{交换a[j]、a[j+1]}1、简洁清晰，可读性好2、不需考虑技术细节（数据抽象、错误处理）3、体现算法的本质4、不会过时牧羊人过河计算流程：分别用M、W、G、C表示人、狼、羊和菜M、W、G、C的初始状态取值0，过河后为1、1、M←G←12、M←0G=13、M←W←1----------------------4、M←G←0W=15、M←C←1----------------------6、M←0W=1C=17、M←G←1M=1G=1汉诺塔算法的伪代码描述Hanoi(n,X,Y,Z)1）IFn=1THENmove(X,Z)ELSE{2）Hanoi(n-1,X,Z,Y)3）move(X,Z)4）Hanoi(n-1,Y,X,Z)}RETURN1.2.4判定树a~ba≥bb~cabb≥ca,b,ca~cbca,c,b,a≥cacc,a,bb~cb,c,aa~cb≥cbcc,b,aa≥cacb,a,c例：将a、b、c三个数排成非递增序算法控制结构1、顺序2、选择3、循环4、子过程调用1.3算法的时间复杂性1、算法分析是指对一个算法所需要的资源进行预测。资源：内存、通信带宽、计算机硬件计算时间对于一个问题，需要选择最有效的算法2、计算模型：包括描述所用的资源及其代价的模型。􀁹RAM（Random-accessMachine,随机存储机）计算模型①指令一条接一条地执行，没有并发操作；②包含了真实计算机中常见的指令，每条指令所需要的时间为常量；③数据类型包括整数类型、浮点实数类型；④没有试图对当代计算机常见的存储器层次进行建模3、运行时间影响因素：数据的规模、输入的分布算法的运行时间：在特定输入时，所执行的基本操作步。1）基本操作独立于机器2）执行第i条指令的时间为常数时间Ci本课程主要对算法的时间复杂性行分析。关于算法的复杂性，有两个问题要弄清楚：(1)用怎样的一个量来表达一个算法的复杂性。(2)对于给定的一个算法，怎样具体计算它的复杂性。例：顺序查找（从头到尾扫描有n个元素的数组A）proceduresearch(c)/*c是整型数*/{i←0C1常数时间j←lC2whilejndo不超过n次循环{ifA[j]=cthenC3i←jC4breakelsej←j+1C5}returni}折半查找procedureb_search(c，L,U){//U和L分别是要查找的数组下标的上界和下界intfound←0whilefound=0andU≥Ldo{m←(U+L)/2//找数组的居中分量ifc=A[m]thenfound←1elseif(c≥A[m])thenL←m+1elseU←m–1}iffound=1thenreturnmelsereturn0}循环体内的处理为常数时间c，最多循环了多少次？RAM模型包含指令算术、数据移动(赋值、存储、复制)和控制(有条件的和无条件的分支,子程序调用和返回)。每一个这样的指令需要一个固定的时间内。取Cci，顺序查找算法在最坏的情况下的运行时间：Cn时间复杂性是问题规模n的函数，定义为T(n)，则T(n)=Cn=O(n)增长的量级(Orderofgrowth)的上界T(n)=O(n)c~A[n/2]c~A[n/4]c~A[3n/4]~c~A[n/8]c~A[3n/8]…………………………………………………….h有n个内节点的比较树是一棵满二叉树，树高h=log2n+1右图是运行这两种算法的时间曲线。该图表明，当n适当大（nN0）时，算法b_Search比算法Search省时，而且当n更大时，节省的时间急剧增加。分析算法复杂性是为了比较解决同一个问题的不同算法的效率。插入排序算法INSERTION-SORT(A)1for(j=2;j=length[A];j++)c1n-12{key=A[j]c23i=j-1c34while(i0&&A[i]key)i5{A[i+1]=A[i]c56i=i-1c6}7A[i+1]=keyc7}0〈i〈n