《算法设计与分析》-第一章 算法引论

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,算法分析与设计,课程介绍,计划学时：,32+8,教材,王晓东，算法设计与分析，北京：清华大学出版社，,2003.1,参考书目,美,Mark Allen Weiss,数据结构与算法分析,C,语言描述,，冯舜玺译，机械工业出版社，,2004.1,美,Ellis Horowitz,Sartaj,Sahni,Sanguthevar,Rajasekaran,计算机算法（,C+,版）,，冯博琴等译，机械工业出版社，,2006.1,目录,第一讲 算法引论,第二讲 基本数据结构与常用算法,第三讲 递归与分治,第四讲 动态规划,第五讲 贪心算法,第六讲 回溯法,第七讲 分支限界法,第八讲 概率算法、,NP,完全性理论及算法研究和应用现状介绍,第一讲 算法引论,本章主要内容,1.1,什么是算法,1.2,算法与程序的区别,1.3,算法的描述,1.4,算法的性能分析,第一讲 算法引论,1.1,什么是算法,算法（,Algorithm,）一词有,Algorism,衍生而来。,Algorism,原作算术解释，来源于波斯作家,Abu,Jafar,Mahammed,ibn,Musa,al,Kowarizmi,的名字（大约,825,年），他写了一本关于数学的教科书。,第一讲 算法引论,1.1,什么是算法,算法（,Algorithm,）是完成特定任务的有限指令集。它具有五个特性：,1.,输入。由外部提供零个或多个输入量。,2.,输出。至少产生一个输出,3.,确定性。每条指令必须清晰、无歧义。,4.,有穷性。一个算对任何一个输入必须在执行有穷步后终止。,5.,可行性。每条指令必须非常基础，原则上用纸和笔就可以实现。,第一讲 算法引论,1.2,算法和程序的区别,一个计算机程序（,Program,）往往是指用某种计算机语言书写的一个,计算过程,或,算法,，要在计算机上执行。,一个算法有多种描述方式，既可以编成程序在计算机上执行，也可以用其它的工具（笔和纸、算盘等）来执行。一个特定的算法不一定和一个程序有关系。,第一讲 算法引论,1.3,算法的描述,用自然语言表示,用流程图表示（传统流程图和,N-S,图）,用伪代码表示,用计算机语言表示,第一讲 算法引论,1.3,算法的描述,例,1,：有两个数,a,b,，按大小顺序打印它们。,自然语言描述：,步骤,1,：输入,a,b,的值；,步骤,2,：如果,a,b,则先打印,a,，再打印,b,；,否则，先打印,b,，再打印,a,；算法结束。,用自然语言表示算法的特点：通俗易懂，但不严谨，容易产生歧义。,第一讲 算法引论,1.3,算法的描述,用流程图表示：,真,假,开始,a,b,结束,输出,b,a,的值,输入,a,b,的值,输出,a,b,的值,第一讲 算法引论,1.3,算法的描述,用,N-S,图表示：,用基本结构的组合表示算法，从而去掉了流程线。避免了随意的跳转。,1973,年两名美国学者提出了一种新的流程图形式，并用二人名字的第一个字母组合命名了该流程图。即,N-S,流程图，也称盒图。,三种基本结构的表示：,P,成立,A,B,A,B,不成立,A,当条件,P,成立时,直到条件,P1,成立,A,第一讲 算法引论,1.3,算法的描述,用,N-S,图表示：,输入,a,b,的值,ab,假,输出,a,b,的值,输出,b,a,的值,真,第一讲 算法引论,1.3,算法的描述,用伪码表示：,例,2,：求,1X2X3X4X5,开始,置,p,的初值为,1,置,i,的初值为,1,当,i,小于,5,时，执行下面的操作：,使,p=p x i,使,i=i+1,打印,p,的值,结束,第一讲 算法引论,1.3,算法的描述,用类计算机语言表示,第一讲 算法引论,1.4,算法的性能分析,几个概念：,问题的规模,n,（,Size of Problem,）,：又称为输入规模（,input size,），是输入量大小的一个测度。,时间复杂度,T(n,),：,算法运行所需的计算时间。,Time Complexity,空间复杂度,S(n,),：,算法运行所需的存储空间。,Space Complexity,第一讲 算法引论,1.4,算法的性能分析,算法的性能评价大致分为两类,（,1,）先验估计（,2,）后验测试，分别称为,性能分析和性能度量。,第一讲 算法引论,1.4,算法的性能分析,渐近符号：,O,、,、,、,o,设,f(n,),和,g(n,),是定义在正数集上的非负函数。,O,（,big O,）,-,f(n,)=,O(g(n,)(,读作,f(n,),是,g(n,),的大,O),当且仅当存在两个正常数,C,和,n,0,，使得对所有的,n,n,0,有,f(n,),C*,g(n,),。,（,omega,）,-,f(n,)=,(g(n,)(,读作,f(n,),是,g(n,),的,omega),当且仅当存在两个正常数,C,和,n,0,，使得对所有的,n,n,0,有,f(n,),C*,g(n,),。,第一讲 算法引论,1.4,算法的性能分析,（,theta,）,-,f(n,)=,(g(n,)(,读作,f(n,),是,g(n,),的,theta),当且仅当存在正常数,C,1,、,C,2,和,n,0,，使得对所有的,n,n,0,有,C,1,*,g(n,),f(n,),C,2,*,g(n,),。,o,（,small o,）,-,f(n,)=,o(g(n,)(,读作,f(n,),是,g(n,),的小,o),当且仅当,第一讲 算法引论,1.4,算法的性能分析,O(1),表示计算时间为常数。,O(n,),称为线性阶。,O(n,2,),称为二次阶。,O(n,3,),称为三次阶。,O(2,n,),称为指数阶。,