第7章算法与程序设计资料.ppt

算法评价 正确性 时间复杂度（计算机上运行所花费的时间）** 空间复杂度（算法运行过程中临时占用的存储空间的大小） 测定运行时间最可靠的方法就是计算对运行时间有消耗的基本操作（如“运算”、“条件比较”、“变量代入”）的执行次数，运行时间与该计数成正比。 算法的复杂度标记方法一般采用“O记法”。在O记法中，算法的复杂度是以处理对象数据的数量n为基准来记述的。 【例】求1+2+3+…+100 普通求和中，数据量为n时，时间复杂度是1+1+(n+1)+n+n=3n+3，操作次数为3n+3。 当n无限增大时，n的系数3和需要加的3均可忽略，因此记做时间复杂度为O(n)。 解决方案1（普通求和） int sum = 0, n = 100; for (int i = 1; i = n; i++) { ? ? ? ? ? ? ? ? ? ? ? ? sum += i; ? ? ? ? }? ? ? ? ? ? ? ? printf( sum = %d, sum); 时间复杂度是1+1+1=3，记做O(3)，与n的值没有关系，因此效率很高。 解决方案2（高斯求和） main() { int sum = 0,n = 100,; ? ? ? sum = (n*(n + 1))/2; ? ? ? printf(sum = %d, sum); ? ? ? } 用自然语言描述算法 用流程图描述算法 用N-S图描述算法 用伪代码表示算法 用计算机语言表示算法 算法的描述方法 用自然语言描述算法 设变量sum为被加数，变量i为加数，用循环算法来求结果。 步骤1：使sum为0，写成0=sum； 步骤2：使i为1； 步骤3：将sum与i相加，结果仍放到变量sum中，写成sum+i=sum； 步骤4：使i的值加1，即i+1=i； 步骤5：如果i的值不大于11（i≤10），返回重新执行第3步和其后的步骤4和步骤5；否则，算法结束，sum的值即为所求。 方法一： 步骤1：先求1与2的和，得到结果3； 步骤2：将步骤1得到的和与3相加，得到结果6； 步骤3：将步骤2得到的和与4相加，得到结果10； … 步骤9：将步骤8得到的和与10相加，得到结果55。 流程图是通过箭头相互连接的几何图形来表达的方法。 ANSI规定的一些常用流程图符号。 起止框 输入输出框 判断框 处理框 流程线 1.认识算法─算法的描述工具 sum=0 n=1 n=10 sum=sum+n n=n+1 输出sum N Y 结束 开始 【示例7-1】求1+2+3+…+10，即 流程图 sum=0，n=1 sum=sum+n n=n+1 输出sum的值 当i=10时，做 N-S图 用流程图/N-S图表示算法 【示例7-1】求1+2+3+…+10，即 #include stdio.h main() { int sum=0,n=1; for(n=1;n=10;n++) { sum=sum+n; } printf(sum=%d\n,sum); } 用计算机语言表示算法 【算法思想】 扫描整个序列，从中选出最小的元素，将它与序列的第一个元素交换； 然后再在余下的元素中找出最小数据的元素，与序列的第二个元素相互交换位置 然后对剩下的序列采用同样的方法，直到序列空为止。 2.经典算法 排序算法：选择排序 #include stdio.h main() { int i,index,k,n,temp,a[5]; printf(“Please input 5 numbers:\n”); for(k=0;k5;k++) scanf(%d,a[k]); for(k=0;k4;k++) { index=k; for(i=k+1;i5;i++) if(a[i]a[index]) index=i; if(index!=k) { temp=a[index]; a[index]=a[k]; a[k]=temp; } } 内循环 外循环 选择法排序 printf(\n); for(k=0;k5;k++) printf(%d,a[k]); } 【算法思想】 在每一轮的排序过程中从第一个数开始，相邻两数依次比较，当发现前一个数据比后一个数据大时，即将这两个数据进行互换。 较小的数据就会逐个向前移动，大者往后移动，最后将序列中的最大值换到了序列的最后。 经典排序算法：冒