《10算法分析》由会员分享，可在线阅读，更多相关《10算法分析（62页珍藏版）》请在金锄头文库上搜索。
1、算法,算法和算法分析,小结和作业,算法分析,算法:是为了解决某类问题而规定的一个有限长的操作序列,算法的定义,输入 输出 有穷性 确定性 可行性,算法的特点,输入:作为算法加工对象的量值，通常体现为算法中的一组变量。算法有0个或多个输入,输出：它是一组与“输入”有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。算法有一个或多个输出。,算法的特点,有穷性:对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即：算法中的每个步骤都能在有限时间内完成。,算法的特点,确定性:对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执
2、行。并且在任何条件下，算法都只有一条执行路径。,算法的特点,可行性:算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。,算法的特点,算法,Algorithm:Out = Translation(In),计算机科学是研究解决具体问题的算法的科学。 或者，是研究信息变换的科学。,算法设计的原则,设计算法时，通常应考虑达到以下目标：,1正确性,2. 可读性,3健壮性,4高效率与低存储量需求,正确性,首先，算法应当满足以特定的“规格说明”方式给出的需求。,其次，对算法是否“正确”的理解可以有以下四个层次：,a程序中不含语法错误,b程序对于几组输入数据能够得出满足要求的结果,
3、c程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果；,通常以第 c 层意义的正确性作为衡量一个算法是否合格的标准。,d程序对于一切合法的输入数据都能得出满足要求的结果；,正确性,可读性,算法主要是为了人的阅读与交流，其次才是为计算机执行。因此算法应该易于人的理解。另一方面，晦涩难读的程序易于隐藏较多错误而难以调试。,健壮性,当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而不是产生莫名奇妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。,高效率与低存储量需求,通常，效率指的是算法
4、执行时间。存储量指的是算法执行过程中所需的最大存储空间。两者都与问题的规模有关。,实例,假设有n个整数，a1，a2，an，并且： a1a2a3an。,任意给定一个整数x，判断x是否与上述n个整数中的某个整数相等，如果是，则给出其下标值，否则，返回0。,算法(Algorithm)一,输入：n个整数a1 a2 an， 整数x 输出：整数i，0 i n,过程： 1、i=1 2、如果ai = x，则输出i，结束 3、i=i+1 4、如果 i n，则重复2-3，否则，输出0，结束,数据结构,用顺序线性表L存放n个数 a1 L.elem0 a2 L.elem1 ai L.elemi-1 ,程序,int l
5、ocate(SqList L, int x),for(i=1; i=L.length; i+),if(x = L.elemi-1) return i;,return 0;,算法二,输入：n个整数a1 a2 an整数x 输出：整数p，0 p n,算法二,过程： 1、i=1, j=n 2、p=(i+ j) / 2 3、如果ap = x，则输出p，结束 4、如果 ap x，则 i=p+1，否则j=p-1 5、如果i j，重复2-4 6、输出0，结束,数据结构,用顺序线性表L存放n个数 a1 L.elem0 a2 L.elem1 ai L.elemi-1 ,程序,int locate(SqList L
6、, int x),i=1, j=L.length;,while(i=j),p=(i + j ) / 2;,if(L.elemp-1 = = x) return p;,if(L.elemp-1 x) i=p+1; elsej=p-1;,return 0,算法分析,算法分析：对算法的执行时间和需要的存储空间进行定性分析，以比较算法、改进算法。,效率分析：计时法渐进表示法,计时法,1、编写程序实现算法,2、记录程序开始执行的时刻t1,3、记录程序结束的时刻t2,4、程序执行时间=t2 - t1,计时法,int locate(SqList L, int x),for(i=1; i=L.length;
7、i+),if(x = L.elemi-1) return i;,return 0;,time_t t1, t2;,time(,time(,printf(“time=%l“, time_t(t2-t1);,#include ,计时法,1、与硬件有关,2、与软件有关,3、与执行时的环境有关,一般是在同一台机器上，多次执行程序，取其平均数作为执行时间，对算法进行比较。,渐进表示法-分析模型,任何一个算法都是由有限个基本运算（算术运算、逻辑运算和赋值操作）组成。,为了分析方便，将每种运算所需要的时间统一定义为1个单位。,算法需要的执行时间为所有运算个数之和,一般的讲，执行时间与问题规模n有关，是n的函
8、数，记作T(n)， T(n)是非负递增函数,分析模型,算法的执行时间与输入是密切相关的Tbest(n)Tworst(n)Taverage(n),Tbest(n) Taverage(n) Tworst(n),算法分析,int locate(SqList L, int x),for(i=1; i=L.length; i+),if(x = L.elemi-1) return i;,return 0;,算法分析,语句if(x = L.elemi-1) return i执行了n（length）次，因此，逻辑运算执行了n次,需要时间为n,语句for(i=1; i=L.length; i+)由三部分构成：,
9、i=1执行一次，时间为 1,i=L.length和i+执行了n次，时间为2n,需要时间为2n + 1,算法分析,忽略掉函数进入和返回需要的时间,T(n) = n+2n+1=3n+1,算法分析,int locate(SqList L, int x),i=1, j=L.length;,while(i=j),p=(i + j ) / 2,if(L.elemp-1 = = x) return p;,if(L.elemp-1 x) i=p+1; elsej=p-1;,return 0,算法分析,语句i=1, j=L.length需要的时间为2,执行一次while需要的时间为7,p=(i + j ) /
10、2;,if(L.elemp-1 = = x) return p;,if(L.elemp-1 x) i=p+1; elsej=p-1;,while(iT2(n) ?,3n + 1 7log2(n-1)+ 16 ?,时间复杂度,T(n)=O(f(n)，如果存在正常数c和n0，当nn0 ，T(n)cf(n),O(f(n)叫做T(n)的 渐近上界( Asymptotic Upper Bound),O(f(n)是一个无穷集合，其元素为函数 例如，O( n2)，n2是集合中的一个代表，集合中任何一个函数f，有cf n2,时间复杂度,T1(n) =3n+1 3n + n4n,c=4，n0 = 1,T1(n)
11、 =O(n),T1(n) =3n+1,时间复杂度,T2(n)= 7log2(n-1)+ 16,T2(n)= O(log2(n) c=8, n0=216,T2(n) = 7log2(n-1)+ 167log2(n) + 167log2(n) + log2(n) n2168log2(n),时间复杂度,T(n)=(g(n)，如果存在正常数c和n0，当nn0 ，T(n)cg(n),(g(n)叫做T(n)的渐近下界(Asymptotic Lower Bound),T1(n)=(n) T2(n)= (log2n),时间复杂度,T(n)=(h(n)，如果存在正常数c1、c2和n0， nn0，c1h(n) T
12、(n) c2h(n),T1(n)= (n) T2(n)= (log2n),常数阶 (1) 对数阶 (log2n) 线性阶 (n) 线性对数阶 (nlog2n) 平方阶 (n2) 立方阶 (n3) k次方阶 (nk) 指数阶 (2n),常见阶列表,时间复杂度,f(x)比g(x)的阶高,f(x)与g(x)同阶,f(x)比g(x)的阶低,f(x)与g(x)不可比,时间复杂度,规则1： 用函数乘以或除以一个正常量不会改变它的阶3n2 和0.2n2 都在(n2),规则2： 加上或减去较低阶的函数不会改变函数的阶2n n + log n 在 (2n),时间复杂度,例题1：比较哪个速度快 T1(n) = a
13、n2 + blogn T2(n) = cn + d,T1(n) = (n2) T2(n) = (n),时间复杂度,例题2：比较哪个速度快 T1(n) = an3 + bn2 + c T2(n) = n(n + 1) / 2,T1(n) = (n3) T2(n) = 0.5n2 + 0.5n =(n2),时间复杂度,例题3：比较哪个速度快 T1(n) = an3 T2(n) = n!,T1(n) = (n3) T2(n) = n!=1*2*3*n1*2*2*2= 2n-1=0.5*2n= (2n),规则1：循环循环次数乘以循环体需要的时间,时间复杂度,规则2：嵌套循环从内循环到外循环逐步分析for(i = 0; i n; i+)for(j = 0;j n; j+)k+,规则3：顺序语句各语句执行时间之和for(i = 0; i n; i+)ai = 0;for(i = 0; i n; i+)for(j = 0; j =1;i-) 语句1 x:=x+1; 语句2for (int j=n;j=i;j-) 语句3y:=y+1; 语句4 ,语句1、2、3、4执行的频度分别为、。,n+1,n,n(n+3)/2,
