资源预览内容
第1页 / 共38页
第2页 / 共38页
第3页 / 共38页
第4页 / 共38页
第5页 / 共38页
第6页 / 共38页
第7页 / 共38页
第8页 / 共38页
第9页 / 共38页
第10页 / 共38页
亲,该文档总共38页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
第1章 算法概述,学习要点: 理解算法的概念。 理解什么是程序,程序与算法的区别和内在联系。 掌握算法的计算复杂性概念。 掌握算法渐近复杂性的数学表述。 掌握用C+语言描述算法的方法。,算法(Algorithm),算法是指解决问题的一种方法或一个过程。 算法是若干指令的有穷序列,满足性质: (1)输入:有外部提供的量作为算法的输入。 (2)输出:算法产生至少一个量作为输出。 (3)确定性:组成算法的每条指令是清晰,无歧义的。 (4)有限性:算法中每条指令的执行次数是有限的,执行每条指令的时间也是有限的。,程序(Program),程序是算法用某种程序设计语言的具体实现。 程序可以不满足算法的性质(4)。 例如操作系统,是一个在无限循环中执行的程序,因而不是一个算法。 操作系统的各种任务可看成是单独的问题,每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。,问题求解(Problem Solving),理解问题,精确解或近似解 选择数据结构 算法设计策略,设计算法,算法复杂性分析,算法复杂性 = 算法所需要的计算机资源 算法的时间复杂性T(n); 算法的空间复杂性S(n)。 其中n是问题的规模(输入大小)。,算法的时间复杂性,(1)最坏情况下的时间复杂性 Tmax(n) = max T(I) | size(I)=n (2)最好情况下的时间复杂性 Tmin(n) = min T(I) | size(I)=n (3)平均情况下的时间复杂性 Tavg(n) = 其中I是问题的规模为n的实例,p(I)是实 例I出现的概率。,算法渐近复杂性,T(n) , as n ; (T(n) - t(n) )/ T(n) 0 ,as n; t(n)是T(n)的渐近性态,为算法的渐近复杂性。 在数学上, t(n)是T(n)的渐近表达式,是T(n)略去低阶项留下的主项。它比T(n) 简单。,渐近分析的记号,在下面的讨论中,对所有n,f(n) 0,g(n) 0。 (1)渐近上界记号O O(g(n) = f(n) | 存在正常数c和n0使得对所有n n0有:0 f(n) cg(n) (2)渐近下界记号 (g(n) = f(n) | 存在正常数c和n0使得对所有n n0有:0 cg(n) f(n) ,(3)非紧上界记号o o(g(n) = f(n) | 对于任何正常数c0,存在正数和n0 0使得对所有n n0有:0 f(n)0,存在正数和n0 0使得对所有n n0有:0 cg(n) f(n) 等价于 f(n) / g(n) ,as n。 f(n) (g(n) g(n) o (f(n),(5)紧渐近界记号 (g(n) = f(n) | 存在正常数c1,c2和n0使得对所有n n0有:c1g(n) f(n) c2g(n) 定理1: (g(n) = O (g(n) (g(n),渐近分析记号在等式和不等式中的意义,f(n)= (g(n)的确切意义是:f(n) (g(n)。 一般情况下,等式和不等式中的渐近记号(g(n)表示(g(n)中的某个函数。 例如:2n2 + 3n + 1 = 2n2 + (n) 表示 2n2 +3n +1=2n2 + f(n),其中f(n) 是(n)中某个函数。 等式和不等式中渐近记号O,o, 和的意义是类似的。,渐近分析中函数比较,f(n)= O(g(n) a b; f(n)= (g(n) a b; f(n)= (g(n) a = b; f(n)= o(g(n) a b.,渐近分析记号的若干性质,(1)传递性: f(n)= (g(n), g(n)= (h(n) f(n)= (h(n); f(n)= O(g(n), g(n)= O (h(n) f(n)= O (h(n); f(n)= (g(n), g(n)= (h(n) f(n)= (h(n); f(n)= o(g(n), g(n)= o(h(n) f(n)= o(h(n); f(n)= (g(n), g(n)= (h(n) f(n)= (h(n);,(2)反身性: f(n)= (f(n); f(n)= O(f(n); f(n)= (f(n). (3)对称性: f(n)= (g(n) g(n)= (f(n) . (4)互对称性: f(n)= O(g(n) g(n)= (f(n) ; f(n)= o(g(n) g(n)= (f(n) ;,(5)算术运算: O(f(n)+O(g(n) = O(maxf(n),g(n) ; O(f(n)+O(g(n) = O(f(n)+g(n) ; O(f(n)*O(g(n) = O(f(n)*g(n) ; O(cf(n) = O(f(n) ; g(n)= O(f(n) O(f(n)+O(g(n) = O(f(n) 。,规则O(f(n)+O(g(n) = O(maxf(n),g(n) 的证明: 对于任意f1(n) O(f(n) ,存在正常数c1和自然数n1,使得对所有n n1,有f1(n) c1f(n) 。 类似地,对于任意g1(n) O(g(n) ,存在正常数c2和自然数n2,使得对所有n n2,有g1(n) c2g(n) 。 令c3=maxc1, c2, n3 =maxn1, n2,h(n)= maxf(n),g(n) 。 则对所有的 n n3,有 f1(n) +g1(n) c1f(n) + c2g(n) c3f(n) + c3g(n)= c3(f(n) + g(n) c32 maxf(n),g(n) = 2c3h(n) = O(maxf(n),g(n) .,算法渐近复杂性分析中常用函数,(1)单调函数 单调递增:m n f(m) f(n) ; 单调递减:m n f(m) f(n); 严格单调递增:m f(n). (2)取整函数 x :不大于x的最大整数; x :不小于x的最小整数。,取整函数的若干性质,x-1 0,有: n/a /b = n/ab ; n/a /b = n/ab ; a/b (a+(b-1)/b; a/b (a-(b-1)/b; f(x)= x , g(x)= x 为单调递增函数。,(3)多项式函数 p(n)= a0+a1n+a2n2+adnd; ad0; p(n) = (nd); f(n) = O(nk) f(n)多项式有界; f(n) = O(1) f(n) c; k d p(n) = O(nk) ; k d p(n) = (nk) ; k d p(n) = o(nk) ; k d p(n) = (nk) .,(4)指数函数 对于正整数m,n和实数a0: a0=1; a1=a ; a-1=1/a ; (am)n = amn ; (am)n = (an)m ; aman = am+n ; a1 an为单调递增函数; a1 nb = o(an),ex 1+x; |x| 1 1+x ex 1+x+x2 ; ex = 1+x+ (x2), as x0;,(5)对数函数 log n = log2n; lg n = log10n; ln n = logen; logkn = (log n)kl; log log n = log(log n); for a0,b0,c0,|x| 1 for x -1, for any a 0, , logbn = o(na),(6)阶乘函数 Stirlings approximation,算法分析中常见的复杂性函数,小规模数据,中等规模数据,算法分析方法,例:顺序搜索算法,template int seqSearch(Type *a, int n, Type k) for(int i=0;in;i+) if (ai=k) return i; return -1; ,(1)Tmax(n) = max T(I) | size(I)=n =O(n) (2)Tmin(n) = min T(I) | size(I)=n =O(1) (3)在平均情况下,假设: (a) 搜索成功的概率为p ( 0 p 1 ); (b) 在数组的每个位置i ( 0 i n )搜索成功的概率相同,均为 p/n。,算法分析的基本法则,非递归算法: (1)for / while 循环 循环体内计算时间*循环次数; (2)嵌套循环 循环体内计算时间*所有循环次数; (3)顺序语句 各语句计算时间相加; (4)if-else语句 if语句计算时间和else语句计算时间的较大者。,template void insertion_sort(Type *a, int n) Type key; / cost times for (int i = 1; i =0 / c7 n-1 ,在最好情况下,ti=1, for 1 i n; 在最坏情况下,ti i+1, for 1 i n;,对于输入数据ai=n-i,i=0,1,n-1,算法insertion_sort 达到其最坏情形。因此, 由此可见,Tmax(n)= (n2),最优算法,问题的计算时间下界为(f(n),则计算时间复杂性为O(f(n)的算法是最优算法。 例如,排序问题的计算时间下界为(nlogn),计算时间复杂性为O(nlogn)的排序算法是最优算法。 堆排序算法是最优算法。,递归算法复杂性分析,int factorial(int n) if (n = 0) return 1; return n*factorial(n-1); ,课后作业,习题 1-7,1-8,1-10。,
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号