算法几何和设计(研究生)全册配套ppt课件

举报
资源描述
算法几何和设计算法几何和设计(研究生研究生)全册配套课件全册配套课件算法设计与分析算法设计与分析 Design and Analysis of Computer Algorithm3参考教材王晓东算法设计与分析(第2版),清华大学出版社,2008周培德计算几何算法分析与设计(第2版)清华大学出版社,2005第一章第一章 算法概述算法概述第二章第二章 递归与分治策略递归与分治策略第三章第三章 动态规划动态规划第四章第四章 贪心算法贪心算法第五章第五章 回朔法回朔法第六章第六章 分支限界法分支限界法第七章第七章 概率算法概率算法第八章第八章 NPNP完全性理论简介完全性理论简介算法设计与分析算法设计与分析 目录目录算算 法法 概概 述述Algorithm Introduction第一章第一章介绍算法设计的基本概念介绍算法设计的基本概念及算法分析的方法和准则及算法分析的方法和准则.算法设计与分析算法设计与分析6一系列将问题的输入转换为输出的计算或操作步骤一系列将问题的输入转换为输出的计算或操作步骤。2.计算机算法与人工算法计算机算法与人工算法算法设计与分析算法设计与分析 算法概述算法概述1.1 算法 Algorithm1.算法定义算法定义有些问题没有计算机算法有些问题没有计算机算法.有些问题计算机算法与人工算法不同有些问题计算机算法与人工算法不同.2).确定性definiteness 算法的每个步骤必须有明确的意义算法的每个步骤必须有明确的意义,对每种可能的情况对每种可能的情况,算法都算法都 要给出确定的操作要给出确定的操作.1).有穷性finiteness 算法必须在执行有穷步后终止算法必须在执行有穷步后终止,且每一步均在有限时间内完成且每一步均在有限时间内完成 3).能行性effectiveness 算法中的每个步骤是能够实现的算法中的每个步骤是能够实现的,算法执行结果要达到预期目的算法执行结果要达到预期目的 3.3.计算机算法的一般特征计算机算法的一般特征 4).有有0 0个或多个输入项个或多个输入项,至少有一个输出项至少有一个输出项.7算法设计与分析算法设计与分析 算法概述算法概述数值型算法数值型算法:算法中的基本运算为算术运算算法中的基本运算为算术运算.非数值型算法非数值型算法:算法中的基本运算为逻辑运算算法中的基本运算为逻辑运算.串行算法串行算法:串行计算机上执行的算法串行计算机上执行的算法.并行算法并行算法:并行计算机上执行的算法并行计算机上执行的算法.从处理方式上从处理方式上6.算法分类算法分类从解法上从解法上5.算法描述语言 1).数据数据:运算序列中作为运算对象和结果的数据运算序列中作为运算对象和结果的数据.2).运算运算:运算序列中的各种运算运算序列中的各种运算:赋值赋值,算术和逻辑运算算术和逻辑运算 3).控制和转移控制和转移:运算序列中的运算序列中的控制和转移控制和转移.4.算法的三个要素自然语言自然语言,数学语言数学语言,流程图流程图,程序设计语言等等程序设计语言等等.8算法设计与分析算法设计与分析 算法概述算法概述7.问题的求解过程2)建立数学模型(UML)1)问题的陈述3)算法设计4)算法的正确性证明5)算法的程序实现6)算法分析用科学规范的语言用科学规范的语言,对所求解的问题做准确的描述对所求解的问题做准确的描述.通过对问题的分析通过对问题的分析,找出其中的所有操作对象及操作对象之间找出其中的所有操作对象及操作对象之间的关系并用数学语言加以描述的关系并用数学语言加以描述.根据数学模型设计问题的计算机求解算法根据数学模型设计问题的计算机求解算法.证明算法对一切合法输入均能在有限次计算后产生正确输出证明算法对一切合法输入均能在有限次计算后产生正确输出.对执行该算法所消耗的计算机资源进行估算对执行该算法所消耗的计算机资源进行估算.将算法正确地编写成机器语言程序将算法正确地编写成机器语言程序.9算法设计与分析算法设计与分析 算法概述算法概述1.2 1.2 算法复杂性分析算法复杂性分析1.复杂性的计量显然显然,它与问题的规模它与问题的规模,算法的输入数据及算法本身有关算法的输入数据及算法本身有关.将时间复杂性和空间复杂性分别考虑将时间复杂性和空间复杂性分别考虑,并用并用T和和S表示表示.则则 T=T(N,I,A)S=S(N,I,A)将将A隐含在函数名中隐含在函数名中,则则 T=T(N,I,A)简化为简化为T=T(N,I)算法的复杂性:算法执行所需的时间和空间的数量算法执行所需的时间和空间的数量.令令 N:问题的规模问题的规模 I:输入数据输入数据 A:算法本身算法本身 则算法的复杂性则算法的复杂性 C=F(N,I,A)设一台抽象计算机提供的元运算有设一台抽象计算机提供的元运算有k种种,分别记作分别记作O1,Ok 设这些元运算每执行一次所需时间分别为设这些元运算每执行一次所需时间分别为t1,t2,tk,设算法设算法A中用到中用到Oi的次数为的次数为 ei,i=1,k,则则 ei=ei(N,I)T=T(N,I)=10算法设计与分析算法设计与分析 算法概述算法概述 算法的复杂性最好情况最好情况:Tmin(N)=T(N,I)=最坏情况最坏情况:Tmax(N)=T(N,I)=平均情况平均情况:Tavg(N)=例例 题题1-1其中其中 DN:规模为规模为N的所有合法输入的集合的所有合法输入的集合 I*:DN中达到中达到Tmax(N)的一个输入的一个输入 :DN中达到中达到Tmin(N)的一个输入的一个输入 P(I):出现输入为出现输入为I的概率的概率算法设计与分析算法设计与分析已已知知不不重重复复且且从从小小到到大大排排列列的的m个个整整数数的的数数组组A1.m,m=2K,K为为正正整整数数.对对于于给给定定的的整整数数c,要要求求找找到到一一个个下下标标i,使使得得Ai=c.找找不不到到返返回回0.functionsearch(c)i:=1;awhileAicandi=Ldo t(logm+2)i:=(L+U)div2;(a+s+d)(logm+1)ifc=Ait(logm+1)thenfound:=trueaelseifcAit(logm+1)thenL:=i+1(s+a)(logm+1)elseU:=i-1iffoundathenb-search:=ielseb-search:=0a在数学上在数学上,T(n)与与 有相同的最高阶项有相同的最高阶项.可取可取 为略去为略去T(n)的的低阶低阶项后剩余的主项项后剩余的主项.当当n充分大时我们用充分大时我们用 代替代替T(n)作为算法复杂性作为算法复杂性的度量的度量,从而简化分析从而简化分析.设设T(n)为算法为算法A的时间复杂性函数的时间复杂性函数,则它是则它是n的单增函数的单增函数,如果存在一如果存在一个函数个函数 使得当使得当n ,有有 (T(n)-)/T(n)0称称 是是T(n)当当 n 时的时的渐进性态或或 渐进复杂性.13算算法设计与分析分析 算法概述算法概述 算法的复杂性2复杂性的渐进性态1).渐进性态 例如例如 T(n)=3n2+4nlogn+7,则则可以是3n2.若进一步假定算法中所有不同元运算的单位执行时间相同若进一步假定算法中所有不同元运算的单位执行时间相同,则可不考则可不考虑虑 所包含的系数或常数因子。所包含的系数或常数因子。渐进分析适用于渐进分析适用于n n充分大的情况充分大的情况,当问题的规模很小时当问题的规模很小时,或比较的两算或比较的两算法同阶时法同阶时,则不能做这种简化则不能做这种简化.14算算法设计与分析分析 算法概述算法概述 算法的复杂性2).渐进性态的阶又如算法又如算法1-11-1中中Tmin(m)=2a+3t,Tmax(m)=(m+1)a+(2m+1)t+(m-1)s,Tmin(m)=O(1)Tmax(m)=O(m)例如例如 3n=O(n),n+1024=O(n),n2=O(n3)?n3=O(n2)?2n2+11n-10=O(n2)若若存存在在正正常常数数c和和自自然然数数N0 使使得得当当 N N0 时时,有有f(N)cg(N)则则称称函函数数 f(N)在在N充充分分大大时时有有上上界界,且且 g(N)是是它它的的一一个个上上界界,记记 为为 f(N)=O(g(N),也也 称称 f(N)的的阶阶不不 高高 于于g(N)的的阶阶.设设f(N)和和 g(N)是定义在正整数集上的正函数是定义在正整数集上的正函数,(1)大大O表示法表示法(算法运行时间的上限)15算算法设计与分析分析 算法概述算法概述 算法的复杂性例如例如 估计如下二重循环算法在最坏情况下时间复杂性估计如下二重循环算法在最坏情况下时间复杂性T(n)的阶的阶.分析:内循环体只需O(1)时间,故fori:=1tondoforj:=1toidos1,s2,s3,s4;s1,s2,s3,s4为单一赋值语句外循环共需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.如果如果 g(n)=O(f(n),则则 O(f)+O(g)=O(f)5.f=O(f)6.O(cf(n)=O(f(n)运算法则内循环共需16算算法设计与分析分析 算法概述算法概述 算法的复杂性(2)大表示法(算法运行时间的下限)f(N)=(g(N)当且仅当当且仅当 f(N)=O(g(N)且且f(N)=(g(N)称函称函数数f(N)与与g(N)同阶同阶.算法的渐进复杂性的阶对于算法的效率有着决定性的意义算法的渐进复杂性的阶对于算法的效率有着决定性的意义:多项式阶算法多项式阶算法(有效算法有效算法):):时间复杂性与规模时间复杂性与规模N N 的幂同阶的幂同阶.指数阶算法指数阶算法:时间复杂性与规模时间复杂性与规模N N 的一个指数函数同阶的一个指数函数同阶.最优算法最优算法:时间复杂性达到其下界的算法时间复杂性达到其下界的算法.如果如果 正常数正常数c和自然数和自然数N0使得当使得当 N N0 时时,有有f(N)cg(N)则称则称函数函数f(N)在在N充分大时有充分大时有下限下限,且且 g(N)是它的一个下限是它的一个下限,记为记为f(N)=(g(N)也称也称f(N)的的阶阶不低于不低于g(N)的的阶阶。(3)表示法17算算法设计与分析分析 算法概述算法概述 算法的复杂性图1时间函数的增长率常见的多项式阶有常见的多项式阶有:O(1)O(logn)O(n)O(nlogn)O(n2)O(n3)O(2n)O(n!)算法概述算法概述 算法的复杂性 3.渐进分析时间复杂性渐进阶分析的规则:(最坏情况)1).赋值,比较,算术运算,逻辑运算,读写单个变量(常量)只需1单位时间2).执行条件语句ifcthenS1else S2的时间为TC+max(TS1,TS2).3).选择语句caseAofa1:s1;a2:s2;.;am:sm 需要的时间为max(TS1,TS2,.,TSm).4).访问数组的单个分量或纪录的单个域需要一个单位时间一个单位时间.5).执行for循环语句的时间=执行循环体时间执行循环体时间*循环次数循环次数.6).whilec dos(repeats until c)语句时间=(Tc+Ts)*循环次数循环次数.7).用goto从循环体内跳到循环体末或循环后面的语句时,不需额外时间8).过程或函数调用语句对非递归调用,根据调用层次由里向外用规则1-7进行分析;对递归调用,可建立关于T(n)的的递归方程,求解该方程得到T(n).例例 题题1-1算法设计与分析算法设计与分析算法1-2:二分查找(假定c是A的最后一元)例例 题题 1-1分析:问题规模为m,元运算执行时间设为赋值a,判断t,加法s,除法d,减法b.最坏情况Tmax(m)=8a+4t+2s+d+(2a+2s+3t+d)logm=14+8logmfunctionb-search(c)L:=1;U:=m;2found:=false;1whilenotfoundandU=Ldo Logm+
展开阅读全文
温馨提示:
金锄头文库所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
相关资源
正为您匹配相似的精品文档
相关搜索

当前位置:首页 > 办公文档 > 教学/培训


电脑版 |金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号