算法和算法分析

www.kasong-，消毒粉www.youlvjing-，防霉剂，www.a-，www.a-，防腐剂,数据结构DATASTRUCTURE,一算法（Algorithm）算法概念：算法是一个有限的指令集，遵循指令流可以完成特定的功能。,算法基本特性：有穷性：算法经有限步后结束；确定性：每一步必须是确切的；可行性：每一步是可执行的；输入：有0或多个输入值；输出：有1或多个输入值；,1.4算法和算法分析,算法基本特性：有穷性：算法经有限步后结束；确定性：每一步必须是确切的，即在任何条件下，算法都只有一条执行路径。菜谱中“加入食盐少许”，少许是不确切的；如果A6则做A-B；可行性：每一步是可执行的，相当基本的，都可以通过已经实现的基本运算执行有限次来实现之；,1.4算法和算法分析,算法与程序的区别算法是解决问题的一种方法或一个过程，考虑如何将输入转换成输出，一个问题可以有多种算法。程序是用某种程序设计语言对算法的具体实现。,主要区别在：有穷性、正确性和描述方法程序可以是无穷的，例如OS，算法是有穷的；程序可以是错误的，算法必须是正确的；程序是用程序设计语言描述，在机器上可以执行；算法还可以用框图、自然语言等方式描述。,1.4算法和算法分析,二、算法的描述和实现描述-可采用自然语言、数学语言或约定的符号语言。实现-必须借助程序设计语言提供的数据类型及其运算。本课的描述-采用类C语言。,1.4算法和算法分析,算法研究涉及两方面内容：设计技术：如何设计一个有效的算法分析技术：评价和判断已有算法的优劣,1.4算法和算法分析,三算法分析如何衡量一个算法的好坏？衡量的四个尺度：正确性:问题的任何一个实例作为输入，算法都能得到正确的结果作为输出；时间特性:运行所花费的时间；空间特性:所占用存储空间的大小；其他（可读性、易调性、健壮性等）。时间和空间特性的巨大改进源于更好的数据结构或算法。,1.4算法和算法分析,算法的时间特性的度量不应依赖算法运行的计算机和软件平台（操作系统、编程语言和编译系统），下面几种度量算法的时间特性的方法被废弃：算法运行的实际执行时间运行过程中所执行的指令条数运行过程中程序循环的次数算法的时间特性用执行基本操作次数来度量。,1.4算法和算法分析,基本操作：是指算法运行中起主要作用且花费最多时间的操作。例如：实数矩阵乘法中，基本操作为实数元素之间的数乘；N个整数排序中，基本操作可以是整数间的比较或数据元素的移动；,1.4算法和算法分析,算法计算量或问题规模：是指算法运行中，输入的规模。例如：实数矩阵乘法中，问题规模为矩阵的阶数（n阶方阵）；排序问题中，问题规模是待排序元素个数；,1.4算法和算法分析,语句频度（FrequencyCount）：语句可能重复执行的最大次数。时间复杂度（TimeComplexity）：设算法中所有语句的语句频度为t(n)，f(n)是当n趋向无穷大时与t(n)为同阶无穷大，则算法的时间复杂度T(n)=O(f(n)其中：n为算法计算量或称为规模（size）；f(n)是运算时间随n增大时的增长率；O(f(n)是算法时间特性的量度。,1.4算法和算法分析,例1：程序段语句频度时间复杂度x:=x+1;1O(1)常数阶FORi:=1TOnDOx:=x+1;n+1O(n)线性阶FORi:=1TOnDOn+1FORj:=1TOnDOx:=x+1;n(n+1)O(n2)平方阶,1.4算法和算法分析,例2分析以下程序段的时间复杂度for(i=1;in;i+)y=y+1;for(j=0;j=(2*n);j+)x+;,/*1*/,/*2*/,1.4算法和算法分析,分析：语句的频度指的是该语句重复执行的次数。一个算法中所有语句的频度之和构成了该算法的运行时间。语句1的频度是：n-1语句2的频度是：,则该程序段的时间复杂度：T(n)=,1.4算法和算法分析,例3分析以下程序段的时间复杂度i=1;while(i=n)i=i*2语句1的频度是：1设语句2的频度是f(n)，则有：即，取最大值则该程序段的时间复杂度为：,/*1*/,/*2*/,例4x=1;for(i=1;i=n;i+)for(j=1;j=i;j+)for(k=1;k=j;k+)x+;由于内循环的执行次数虽与规模n无直接关系，但与外循环的变量取值有关。因此从内层向外层循环分析执行次数。,常见函数的时间复杂度按数量递增排列及增长率。P16图1.7,时间复杂度T(n)按数量级递增顺序为：,复杂度高,复杂度低,当n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。因此，只要有人能将现有指数时间算法中的任何一个算法化简为多项式时间算法，那就取得了一个伟大的成就。,1.4算法和算法分析,四、设计好算法的必要性,一方面计算机性能在不断提高，另一方面用计算机解决应用问题也在不断变化：应用的范围不断扩张（由字符发展为多媒体）应用问题的规模不断增加应用问题本身也越来越复杂,1.4算法和算法分析,以数据搜索为例：50年代，主要用于数值计算，编译系统中符号表的规模不超过1000字节，即为K级；70年代，开始数据管理，数据库中的记录较多，在1000000字节，即M级；90年代，Internet兴起，网上搜索的数据量又大幅增长，超过1000M字节经常遇到，即达到G级；这说明CPU性能的提高相对应用问题的变化，仍是“供不应求”,计算机技术的每一项重大进步都与算法研究的突破有关：多媒体技术与数据压缩算法的研究；声音文件的MP3压缩技术更说明压缩与解压算法的研究成果的巨大成功；信息安全中的关键技术-信息加密算法；许多组合优化问题中，时间复杂度是指数阶，只能靠算法研究来解决。,五、空间复杂度,与时间复杂度类似，空间复杂度是指算法在计算机内执行时所需存储空间的度量。记作:S(n)=O(f(n)我们一般所讨论的是除正常占用内存开销外的辅助存储单元规模。讨论方法与时间复杂度类似，不再赘述。,本章小结数据、数据结构等基本概念数据结构的三个方面的内容抽象数据类型的概念线性和非线性结构的逻辑特征数据存储的四种基本方法算法、算法的时间复杂度及其分析的简易方法,本章小结,数据