第1章算法与程序1.1算法的基本概念1.1.1什么是算法一般的定义：对特定问题的求解方法和步骤，它是指令的有限系列，其中每一指令表示一个或多个有效的操作。D.E.Knuth的定义：一个算法是一个有穷规则的集合，其中的规则定义了解决某一特定类型问题的运算序列。例：求解两个正整数m和n的最大公因子的欧几里德算法。1.1.2算法的基本特性⑴输入//初始化⑵输出//执行结果⑶有穷性//有限步骤⑷确定性//每一步骤是明确的，无歧义⑸有效性（可行性）注意：一个算法是在有限的步骤内完成，且每一个步骤的操作都是有效的、明确的。1.2算法的表示1.2.1自然语言（如上所述欧几里德算法的3步骤）①以m除以n，并令所得余数为r（必有r<n）。②若r为0，输出结果n，算法结束；否则继续步骤③。③令m=n，n=r，返回步骤①，继续进行。优点：易理解；缺点：产生歧义、冗长、不简洁、不直观1.2.2流程图优点：易理解、步骤清晰；缺点：不易表示层次结构、过早考虑流程而忽视数据结构、篇幅大1.2.3N-S图优点：易理解、易表示层次结构和嵌套流程；缺点：过早考虑流程而忽视数据结构、不易修改1.2.4伪代码algorithmEuclidbegininputm,nmmodn→rwhiler≠0dobeginn→mr→nmmodn→rendoutputnend优点：无须严格的语法、简练；缺点：不直观1.2.5程序设计语言#include<iostream>voidmain(){intm,n,r;cout<<”inputm:”;cin>>m;cout<<”inputn:”;cin>>n;r=m%n;while(r!=0){m=n;n=r;r=m%n;}cout<<”thebiggestcommonfactoris”<<n;}优点：可以编译和执行验证；缺点：与自然语言一样，串行描述而不直观1.3算法的设计和评价1.3.1评价算法的标准⑴正确性：满足具体问题的要求，能解决实际问题，结果正确；⑵可读性：可以阅读、理解，便于交流和审核；⑶健壮性（鲁棒性）：能应对异常，控制程序的执行；⑷高效率：既在尽可能短的时间内执行完成，又尽可能地节省存储空间。1.3.2算法的时间和空间效率算法效率的评价时间效率：算法执行耗费CPU的时间来衡量空间效率：算法执行耗费内存空间的大小来衡量时间效率的衡量：⑴事后统计⑵事前分析估算：以基本操作的重复次数与问题规模n的关系作为算法时间的量度。记为：T(n)=O(f(n))---------算法的时间复杂度例：选择排序算法的T(n)分析。#definen100#include<iostream.h>voidswap(inta[n],inti,intj){inttemp;temp=a[i];a[i]=a[j];a[j]=temp;}voidmain(){inti,j,pos,a[n];randomize();for(i=0;i<n;i++)a[i]=random(100);//初始化数组元素cout<<"beforesorting:";for(i=0;i<n;i++)cout<<a[i]<<”,”;cout<<endl;for(i=0;i<n-1;i++){pos=i;for(j=i+1;j<n;j++)if(a[pos]>a[j])pos=j;//比较元素的大小if(pos!=i)swap(a,i,pos);//交换元素}cout<<"aftersorting:";for(i=0;i<n;i++)cout<<a[i]<<”,”;cout<<endl;}此算法的基本操作是元素的比较和交换，其重复次数分别为n(n-1)/2和n-1T(n)=O(n(n-1)/2+n-1)当n→∞时，T(n)/(n(n-1)/2+n-1)→2，T(n)与n2是同数量级选择排序算法的T(n)=O(n2)算法时间复杂度的运算法则：⑴常数法则一：T(n)=O(f(n)+C)=O(f(n))其中C为常数⑵常数法则二：T(n)=O(C*f(n))=O(f(n))⑶求和法则一：若T1(n)=O(f(n))，T2(n)=O(g(n))，则T1(n)+T2(n)=O(max(f(n),g(n)))⑷求和法则二：若T1(m)=O(f(m))，T2(n)=O(g(n))，则T1(m)+T2(n)=O(f(m)+g(n))⑸乘法法则：若T1(n)=O(f(n))，T2(n)=O(g(n))，则T1(n)×T2(n)=O((f(n)×g(n))空间效率的衡量：以算法所需的存储空间对应问