第二章-算法分析基础.pptVIP

算法分析与设计主讲：徐晓蓉邮箱：rortyrong@163.com所在院系：计算机科学与技术学院第2章算法分析基础本章主要内容:第2章算法分析基础第2章算法分析基础第2章算法分析基础第2章算法分析基础第2章算法分析基础第2章算法分析基础第2章算法分析基础第2章算法分析基础第2章算法分析基础第2章算法分析基础第2章算法分析基础第2章算法分析基础第2章算法分析基础*算法复杂度好算法的特征影响程序运行时间的因素如何分析算法的时间复杂度算法分析的渐进表示法使用递推关系分析递归算法2.1算法复杂度算法复杂度:是指运行一个算法所需的时间和空间资源的量.2.1.1什么是好的算法?一个好算法应该具备的特征:正确性:即满足预先规定的功能和性能简单性:算法思路清晰,层次分明,容易理解,易于编码和测试.健壮性:当输入不合法数据时,能适当处理而不引起严重错误高效率低存储:算法应有效使用存储空间,并具有高的时间效率.最优性:算法的执行时间已达到求解该类问题所需时间的下界.2.1算法复杂度算法复杂度:是指运行一个算法所需的时间和空间资源的量.2.1.1什么是好的算法?判断一个算法是否最优的方法:看算法的最坏时间复杂度是否与求解该类问题所需的时间下界相等.如:最大元问题任何通过元素之间的比较的方式来求解此问题的正确算法至少需要进行n-1次元素间的比较,而n-1次元素比较是求最大元问题所需时间的下界，故,任意在最坏情况下只需n-1次元素比较的算法，便是求解该问题的最优算法最优算法不唯一2.1.2影响程序运行时间的因素程序的运行时间:是程序运行从开始到结束所需的时间.影响程序运行时间的因素算法问题规模特定的输入计算机软硬件环境(编译程序,编程语言,CPU运算速度的快慢，内存空间的大小，等等)2.1.3算法的时间复杂度定义:算法运行所需的时间分析方法事先分析:算法运行之前,对它的效率进行分析事后分析:通过运行程序,测试算法实际运行的时间要分析算法的时间复杂度，必须搞清楚以下两个问题:用怎样的一个量来度量算法的时间复杂度(量)给定一个算法,如何具体计算它的复杂性(计算)2.1.3算法的时间复杂度例1:已知整型数组A中含有n个互不相同且已按递增顺序排好序的整数，现要求在数组A中查找某一整数C,若找到，返回相应的下标，若未找到，返回-1.方法:顺序查找法和二分法intsearch(intA[],intn,intC){inti=0;for(i=0;in;i++)if(A[i]==C)break; if(i==n)return-1;elsereturni; }算法1-1:顺序查找分析:当C==A[0]时,只需做1次比较.当C==A[i]时,只需做i+1次比较.当C==A[n-1]时,只需做n次比较.故：最好情况下：Tbest(n)=1；最坏情况下：Tworst(n)=n；算法1-2:二分查找(假定C是A的最后一元)分析:当C==A[mid]时，只需做1次比较.当C==A[n-1]时,需做log2n+1次比较.故：最好情况下：Tbest（n）=1；最坏情况下：Tworst(n)=log2n+1；intb-search(intA[],intn,intC){intlow=0,high=n-1;intmid;while(low=high){mid=(low+high)/2;if(A[mid]==C)returnmid;elseif(A[mid]C)low=mid+1;elsehigh=mid-1;} return-1;}(1)算法时间复杂性的计量：用算法执行基本运算的次数来表示算法的时间复杂度。所谓基本运算：是指算法中最主要最基本的运算与基本运算的次数相关的量：算法问题规模(n)特定输入数据(I).