p7_计算机算法初步.ppt

第5讲 计算机算法初步 5.1 算法的概念 利用计算机求解问题的一般过程 （1）问题分析阶段 （2）数据结构设计阶段 （3）算法设计阶段 （4）编码与调试阶段 算法设计的要求 算法应达到的目标 正确性 可读性 健壮性 效率与低存贮量 算法效率的度量 1) 事后统计法(需先运行程序、统计有赖于计算机软硬环境) 2）事前分析估算法 运行时间取决于如下因素： 算法策略、问题规模、程序语言、编译程序、机器速度 算法的时间复杂度：基本操作（原操作）重复执行的次数。 它是问题规模n的某个函数f(n)： T(n) = O(f(n))（表明随n 的增大，算法执行时间的增长率和f(n)的增长率相同，称做算法的渐进时间复杂度） 语句频度：该语句重复执行的次数 算法的时间复杂度计算: 例1： x+=5; 单个语句的频度为1，则 程序段的时间复杂度为T(n)=O(1)。 三例：两个NxN矩阵相乘 两个NxN矩阵相乘的算法中乘法运算是基本操作，其重复执行的次数为n3。 该算法的时间复杂度为:　T(n) = O(n3)。for (i=1; i=n;++i) for(j=1;j=n;++j){ c[i,j]=0; for(k=1;k=n;++k) c[i,j] += a[i,k]*b[k,j]; }注意：由于算法的时间复杂度只是对于问题规模n的增长率，在难以精确计算语句频度的情况下，只需求出它关于n的增长率或阶即可。 渐近时间复杂度(阶)与语句频度 时间复杂度只考虑对于问题规模的增长率 在难以精确计算基本操作执行次数时, 仅需要求增长率(或阶)即可. 阶： for(i=2; i=n;++i) for(j=2; j=i;++j){++x; a[i, j] = x;} ++x的执行次数关于n 的增长率是O(n2) 语句频度 (n-1) + (n-2) + …… + 2 + 1 = (n-1)n/2 通常涉及的增长率（阶） （从大到小） nn n!（阶乘阶） cn(c1), 2n , 3n（指数阶） nc(c1), n2, n3（方阶） nlog(n), nlog2(n)（对数阶） nr(0r1.0) log(n), log2(n) n(线性阶) 1（常量阶） 算法的重要性 问题：百元买百笔。钢笔3元一支，圆珠笔2元一支，铅笔5角一支。给出解决方案。 方案1： for( i = 0; i =100; i++) for( j = 0; j =100; j++) for( k= 0; k =100; j++) if(i+j+k==100 3*i+2*j+0.5*k==100) printf(“i=%d，j=%d，k=%d”,i,j,k) 算法的重要性 （续） 方案2： for( i = 0; i =20; i++) for( j = 0; j =34-i; j++) if(3*i+2*j+(100-i-j) *0.5==100) printf(“i=%dj=%dk=%d”,i,j, 100-i-j); 方案1 内层循环超过100万次，在某机器上运行了50分钟；方案2 的if语句执行525次，运行了2秒钟，相差1500倍。 算法的存储空间需求 空间复杂度 S(n)=O(f(n)) N为问题的规模表示随着问题规模 n 的增大，算法运行所需存储量的增长率与 f(n) 的增长率相同 空间需求： 存储空间：存放程序、常量、变量和数据 辅助空间：用于执行时 当额外空间相对于输入数据量为常量时，称算法为原地工作。 算法设计的描述 常用流程图符号 例1：求解一元二次方程 问题分析 假设一元二次方程可以书写成ax2+bx+c=0。可以看出，任何一个一元二次方程都由三个系数a、b、c惟一确定，所以，首先需要用户输入三个系数，然后再根据一元二次方程的求解规则计算最终的结果，并将结果显示输出。 算法描述 程序代码 5.2 穷举法 概述 穷举法，又称为枚举法，是人们日常生活中常用的一种求解问题的方法。例如，从某个班中找出所有班干部，需要逐一对每个同学进行查看，判断是否是班干部。这种方法的基本思路就是一一列举每个可能性，逐个进行排查。因此，穷举法的核心在于明确问题的所有可能性，并针对每种可能情况逐个进行判断，最终找出正确问题的答案。 穷举法应用实例1：素数的判断 所谓素数是指仅能被1和自身整除，且大于等