算法引论及简单算法730708126.ppt
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《算法引论及简单算法730708126.ppt》由会员分享,可在线阅读,更多相关《算法引论及简单算法730708126.ppt(36页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、0注注 意意1与数据结构的区别:与数据结构的区别:考虑问题的考虑问题的角度角度:数据结构关心不同的数据结构在解题中的作用和效率;算法关:数据结构关心不同的数据结构在解题中的作用和效率;算法关心不同设计技术的适用性和效率。心不同设计技术的适用性和效率。考虑问题的考虑问题的高度高度:数据结构关心的是解具体问题,算法不仅如此,它提供一种解:数据结构关心的是解具体问题,算法不仅如此,它提供一种解决问题的通用方法。决问题的通用方法。与其他课程的关系与其他课程的关系高级程序设计语言(高级程序设计语言(C语言,等)语言,等)数据结构数据结构 算法设计算法设计与与分析分析 系统的设计与实现系统的设计与实现 2
2、主要内容主要内容o目标:目标:了解算法分析的了解算法分析的了解算法分析的了解算法分析的基本含义基本含义基本含义基本含义。掌握。掌握。掌握。掌握查找算法查找算法查找算法查找算法、排序算法排序算法排序算法排序算法、递推算法递推算法递推算法递推算法等算法理念。等算法理念。等算法理念。等算法理念。提纲提纲补补1.1 1.1 算法分析算法分析补补1.2 1.2 查找算法查找算法补补1.3 1.3 排序算法排序算法补补1.4 1.4 递推算法递推算法3补补1.1 算法分析算法分析o前面的课程内容以前面的课程内容以C语言语法为主语言语法为主o本补充章介绍一些基本算法本补充章介绍一些基本算法o大家在编写程序的
3、时候,大家在编写程序的时候,“八仙过海,八仙过海,各显神通各显神通”,解决同一个问题,可以使,解决同一个问题,可以使用各种方法。用各种方法。o算法之间存在着算法之间存在着“优劣优劣”之分之分4补补1.1 算法分析算法分析1、算法分析的目的算法分析的目的 o通过对算法分析,在把算法变成程序实际运通过对算法分析,在把算法变成程序实际运行前,就知道为完成一项任务所设计的算法行前,就知道为完成一项任务所设计的算法的好坏,从而运行好算法,改进差算法,避的好坏,从而运行好算法,改进差算法,避免无益的人力和物力浪费。免无益的人力和物力浪费。5补补1.1 算法分析算法分析2、算法分析的含义算法分析的含义o算法
4、分析是一种分析技术,它以独立于具体的硬件平算法分析是一种分析技术,它以独立于具体的硬件平台、编译器和编程语言的方式,来描述算法的执行行台、编译器和编程语言的方式,来描述算法的执行行为,即它关心的是算法,而不是程序。为,即它关心的是算法,而不是程序。o算法分析是一种测量算法的性能的方法,它不关心精算法分析是一种测量算法的性能的方法,它不关心精确的细节,如在算法的某次运行中总共执行了多少条确的细节,如在算法的某次运行中总共执行了多少条机器指令,而是想要一个大致的估计,即随着输入数机器指令,而是想要一个大致的估计,即随着输入数据规模的增大,算法所需工作量以何种速度递增。据规模的增大,算法所需工作量以
5、何种速度递增。(关心变化趋势)(关心变化趋势)6补补1.1 算法分析算法分析3、算法复杂性算法复杂性 时间复杂性和空间复杂性时间复杂性和空间复杂性7补补1.1 算法分析算法分析1.有些计算机需要用户提供程序运行有些计算机需要用户提供程序运行时间的上限,一旦达到这个上限,时间的上限,一旦达到这个上限,程序将被强制结束。程序将被强制结束。2.正在开发的程序可能需要提供一个正在开发的程序可能需要提供一个满意的实时响应。满意的实时响应。为什么要考虑时间复杂性?为什么要考虑时间复杂性?81.1.多用户系统中运行时,需指明分配给该程序的内多用户系统中运行时,需指明分配给该程序的内存大小。存大小。2.2.可
6、提前知道是否有足够可用的内存来运行该程序。可提前知道是否有足够可用的内存来运行该程序。3.3.一个问题可能有若干个内存需求各不相同的解决一个问题可能有若干个内存需求各不相同的解决方案,从中择取。方案,从中择取。4.4.利用空间复杂性来估算一个程序所能解决问题的利用空间复杂性来估算一个程序所能解决问题的最大规模。最大规模。考虑程序的空间复杂性的理由:考虑程序的空间复杂性的理由:补补1.1 算法分析算法分析94.如何进行算法分析?如何进行算法分析?o事前分析事前分析:就算法本身,通过对其执行性能的理论分析,:就算法本身,通过对其执行性能的理论分析,得出关于算法特性得出关于算法特性时间和空间时间和空
7、间的一个特征函数(的一个特征函数()与计算机软硬件没有直接关系。与计算机软硬件没有直接关系。o事后测试事后测试:将算法编制成程序后放到计算机上运行,收:将算法编制成程序后放到计算机上运行,收集其执行时间和空间占用等统计资料,进行分析判断集其执行时间和空间占用等统计资料,进行分析判断直接与物理实现有关。直接与物理实现有关。补补1.1 算法分析算法分析101)事前分析)事前分析o目的:试图得出关于算法执行特性的一种形式描目的:试图得出关于算法执行特性的一种形式描 述,以述,以“理论上理论上”衡量算法衡量算法“好坏好坏”。o如何给出反映算法执行特性的描述如何给出反映算法执行特性的描述?最直接方法:最
8、直接方法:统计算法中各种运算的执行情况:统计算法中各种运算的执行情况:运用了哪些运算运用了哪些运算 每种运算被执行的次数每种运算被执行的次数 该种运算执行一次所花费的时间该种运算执行一次所花费的时间 算法的执行时间算法的执行时间=Fi*ti补补1.1 算法分析算法分析11估算执行时间的方法估算执行时间的方法 选择一种或多种(如加、乘和比较等),然后确定这种(些)选择一种或多种(如加、乘和比较等),然后确定这种(些)操作分别执行了多少次。操作分别执行了多少次。令令n代表程序实例特征,则执行时间计算公式为:代表程序实例特征,则执行时间计算公式为:TP(n)=c1ADD(n)+c2SUB(n)+c3
9、MUL(n)+c4DIV(n)+c1、c2、c3、c4分别表示一次加、分别表示一次加、减、乘、减、乘、除操作所需的时间。除操作所需的时间。函数函数ADD(n)、SUB(n)、MUL(n)、DIV(n)分别表示程分别表示程序序P中,所使用的加、减、乘、中,所使用的加、减、乘、除操作的次数。除操作的次数。这种方法是否成功取决这种方法是否成功取决于识别关键操作的能力,于识别关键操作的能力,这些关键操作对时间复这些关键操作对时间复杂性的影响最大。杂性的影响最大。一条语句在整个程序运行时实际执行时间一条语句在整个程序运行时实际执行时间=频率计数频率计数*每执行一次该语句所需的时间每执行一次该语句所需的时
10、间补补1.1 算法分析算法分析12o频率计数:频率计数:算法中算法中语语句句或或运算运算的的执执行次数。行次数。例:例:x=x+y for(i=1;i=n;i+)for(i=1;i=n;i+)x=x+y;for(j=1;j=n;j+)x=x+y;(a)(b)(c)分析:分析:(a):x=x+y执执行了行了1次次 (b):x=x+y执执行了行了n次次 (c):x=x+y执执行了行了n2次次 注:在事前分析中,只限于确定与所使用机器及其他环境因素无关的频率计注:在事前分析中,只限于确定与所使用机器及其他环境因素无关的频率计数,依此建立一种理论上分析模型。数,依此建立一种理论上分析模型。补补1.1
11、算法分析算法分析13o数量级数量级语句的数量级语句的数量级:语句的执行频率。:语句的执行频率。例:例:1,n,n2 算法的数量级算法的数量级:算法包含所有语句的执行频率之和。:算法包含所有语句的执行频率之和。算法的数量级从本质上反映了一个算法的执行特性。算法的数量级从本质上反映了一个算法的执行特性。例:求解同一问题的三个算法分别具有例:求解同一问题的三个算法分别具有n,n2,n3数量级。数量级。若若n=10,则可能的执行时间将分别是,则可能的执行时间将分别是10,100,1000 个单位时间个单位时间与环境因素无关。与环境因素无关。补补1.1 算法分析算法分析14补补1.1 算法分析算法分析5
12、、算法复杂性的等级算法复杂性的等级o常量阶常量阶n时间复杂度为时间复杂度为O(1)n算法运行时间不随着问题的规模而变化算法运行时间不随着问题的规模而变化n如:如:o简单的赋值语句,简单的赋值语句,x=y;o算术运算,算术运算,x=y*5+z%3;o固定次数的循环语句等固定次数的循环语句等for(i=0;i10;i+)for(j=0;j20;j+)aij=0;15补补1.1 算法分析算法分析o线性阶线性阶n时间复杂度为时间复杂度为O(n)n算法运行时间随着问题的规模而成线性变化算法运行时间随着问题的规模而成线性变化for(i=0;in;i+)sum=sun+i;算法执行了多少次运算?算法执行了多
13、少次运算?i=0;执行了执行了1次次in;执行了执行了n+1次次i+;执行了执行了n次次sum=sun+i;执行了执行了n次次共执行了共执行了3n+2次运算次运算时间复杂度就是时间复杂度就是O(3n+2)实际上,算法的时间复杂度并不精确实际上,算法的时间复杂度并不精确计算基本操作的执行次数,它主要考计算基本操作的执行次数,它主要考虑问题规模的增长率。虑问题规模的增长率。O(n)16补补1.1 算法分析算法分析o平方阶平方阶n时间复杂度为时间复杂度为O(n2)n算法运行时间随着问题的规模而成平方变化算法运行时间随着问题的规模而成平方变化for(i=0;in;i+)for(j=0;jn;j+)su
14、m=sun+aij;/执行执行n2次次printf(“%dn”,sum);/执行执行n次次时间复杂度就是时间复杂度就是O(n2)17补补1.1 算法分析算法分析o多项式阶多项式阶n时间复杂度为时间复杂度为O(nd)d为固定常数为固定常数n算法运行时间随着问题的规模而成算法运行时间随着问题的规模而成d次多项式阶变化次多项式阶变化o对数阶对数阶 O(logn)o指数阶指数阶 O(log2n)o阶乘阶阶乘阶 O(n!)o若若T(n)=adnd+a1n+a0是一个是一个d次多项次多项 式,则有式,则有T(n)=O(nd)185、算法分类算法分类(计算时间)(计算时间)多项式时间算法:多项式时间算法:可
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 引论 简单 730708126
![提示](https://www.taowenge.com/images/bang_tan.gif)
限制150内