第一章算法与程序设计简介.ppt

Visual FoxPro 2. 算法描述举例 【例1.1】 求两个整数a,b(ab)的最大公约数的欧几里德算法: (1) a除以b得余数r;若r=0,则b为所求的最大公约数。 (2) 若r≠0,以b为a,r为b,继续(1)。 注意到任两整数总存在最大公约数,上述辗转相除过程中余数逐步变小,相除过程总会结束。 欧几里德算法又称为“辗转相除”法，具体描述如下： 输入正整数a,b; if(ab) {c=a;a=b;b=c;} /* 交换a,b ,确保ab */ r=a%b; while(r!=0) { a=b;b=r; /* 实施辗转相除 */ r=a%b; } printf(最大公约数b); 算法复杂性的高低体现运行该算法所需计算机资源的多少。 算法的复杂性越高，所需的计算机资源越多；反之，算法的复杂性越低，所需的计算机资源越少。 计算机资源，最重要的是时间资源与空间资源。 需要计算机时间资源的量称为时间复杂度，需要计算机空间资源的量称为空间复杂度。 算法分析是指对算法的执行时间与所需空间的估算，定量给出运行算法所需的时间数量级与空间数量级。 在分析算法时，隐藏细节的数学表示法成为大写O记法 一个算法的时间复杂度是指算法运行所需的时间。一个算法的运行时间取决于算法所需执行的语句（运算）的多少。算法的时间复杂度通常用该算法执行的总的语句（运算）的数量级决定。 就算法分析而言，一条语句的数量级即执行它的频数，一个算法的数量级是指它所有语句执行频数之和。 1. 时间复杂度定义 定义： 对于一个数量级为的 算法，如果存在两个正常数c和m，对所有的n≥m，有 则记作 ，称该算法具有 用 的运行时间，是指当n足够大时，该算法的实际运行时间不会超过的某个常数倍时间。 2. 例如程序段： for(k=1;k=n;k++) { x=x+y; y=x+y; s=x+y; } 每个赋值语句执行频数为n，该算法的数量级为3n； 其计算时间即时间复杂度为O(n)。 3. 例如程序段： for(t=1,k=1;k=n;k++) {t=t*2; for(j=1;j=t;j++) s=s+j; } 内循环赋值语句执行频数 算法的时间复杂度为O( )。 4. 算法时间关系： 常见多项式时间算法: 常见指数时间算法: 一般地，当n取值比较大时，在计算机上实现指数时间算法是不可能的，就是比时间复杂度 高的多项式时间算法运行也很困难。 5. 两个定理 定理1.1 时间复杂度符号O有以下运算规则： O(f)+O(g)=O(max(f,g)) (1.1) O(f)O(g)=O(fg) (1.2) 定理1.2 如果 是n的m次多项式，则 (1.3) 【例1.3】 估算下列程序段代表算法的时间复杂度。 (1) t=1;m=0; for(k=1;k=n;k++) { t=t*2; for(j=t;j=n;j++) m++; } 时间复杂度为O(nlogn). (2) m=0; for(k=1;k=n;k++) for(j=k*k;j=n;j++) m++; 时间复杂度为O( ). 注意(1)、(2)中m++语句的执行次数 的计算，具体见教材详列。 一个算法的运行时间，与问题的规模相关，也与输入的数据相关。 对算法的改进与优化，主要表现在有效缩减算法的运行时间与所占空间。 例如把求解某一问题的算法时间从 优化缩减为 就是一个了不起的成果。 或者把求解某一问题的算法时间的系数缩小，例如从2n缩小为3n/2，尽管其时间数量级都是，系数缩小了也是一个算法改进的成果。 算法的空间复杂度是指算法运行的存储空间，是实现算法所需的内存空间的大小。 一个程序运行所需的存储空间通常包括固定空间需求与可变空间需求两部分。 固定空间需求包括程序代码、常量与结构变量等所占的空间。 可变空间需求包括数组元素所占的空间