第1章主要内容1.1算法与算法描述3.算法是满足下列特性的指令序列：(1)确定性组成算法的每条指令是清晰的，无歧义的。(2)可行性算法中的运算是能够实现的基本运算，每一种运算可在有限的时间内完成。(3)有穷性算法中每一条指令的执行次数有限，执行每条指令的时间有限。(4)输入一个算法有零个或多个输入。(5)输出一个算法至少产生一个量作为输出。4.选择算法的标准1.1.2算法描述2.算法描述举例【例1.1】求两个整数a,b(a>b)的最大公约数的欧几里德算法:(1)a除以b得余数r;若r=0,则b为所求的最大公约数。(2)若r≠0,以b为a,r为b,继续(1)。注意到任两整数总存在最大公约数,上述辗转相除过程中余数逐步变小,相除过程总会结束。欧几里德算法又称为“辗转相除”法，具体描述如下：输入正整数a,b;if(a<b){c=a;a=b;b=c;}/*交换a,b,确保a>b*/r=a%b;while(r!=0){a=b;b=r;/*实施"辗转相除"*/r=a%b;}printf(最大公约数b);算法复杂性的高低体现运行该算法所需计算机资源的多少。算法的复杂性越高，所需的计算机资源越多；反之，算法的复杂性越低，所需的计算机资源越少。计算机资源，最重要的是时间资源与空间资源。需要计算机时间资源的量称为时间复杂度，需要计算机空间资源的量称为空间复杂度。算法分析是指对算法的执行时间与所需空间的估算，定量给出运行算法所需的时间数量级与空间数量级。在分析算法时，隐藏细节的数学表示法成为大写O记法一个算法的时间复杂度是指算法运行所需的时间。一个算法的运行时间取决于算法所需执行的语句（运算）的多少。算法的时间复杂度通常用该算法执行的总的语句（运算）的数量级决定。就算法分析而言，一条语句的数量级即执行它的频数，一个算法的数量级是指它所有语句执行频数之和。1.时间复杂度定义2.例如程序段：for(k=1;k<=n;k++){x=x+y;y=x+y;s=x+y;}每个赋值语句执行频数为n，该算法的数量级为3n；其计算时间即时间复杂度为O(n)。【例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).算法的空间复杂度是指算法运行的存储空间，是实现算法所需的内存空间的大小。一个程序运行所需的存储空间通常包括固定空间需求与可变空间需求两部分。固定空间需求包括程序代码、常量与结构变量等所占的空间。可变空间需求包括数组元素所占的空间与运行递归所需的系统栈空间等。二维或三维数组是空间复杂度高的主要因素之一。在算法设计时，为降低空间复杂度，要注意尽可能少用高维数组。1.2.1算法与程序1.基本概念算法是程序设计的基础，是程序的核心。程序是某一算法用计算机程序设计语言的具体实现。具体来说，一个算法使用C语言描述，就是C程序。上机实践是检验算法与程序的标准。2.程序的内容一个程序应包括对数据的描述与对运算操作的描述两个方面的内容。著名计算机科学家沃思(NikiklausWirth)就此提出一个公式：数据结构＋算法＝程序(1.4)数据结构是对数据的描述，而算法是对运算操作的描述。1.4程序实现求两个整数a,b的最大公约数(a,b)的欧几里德算法(见例1.1)，并应用欧几里德算法求n个整数的最大公约数。解：在欧几里德算法描述基础上进行数据描述即为求整数的最大公约数的程序。(1)求两个整数的最大公约数程序实现设置算法中的相关变量a,b,c,r为长整型变量，即有/*求整数a,b的最大公约数（a,b）*/#include<stdio.h>voidmain(){longa,b,c,r;printf("请输入整数a,b:");scanf("%ld,%ld",&a,&b);/*输入整数a,b*/printf("(%ld,%ld)",a,b);if(a<b){c=a;a=b;b=c;}/*交换a,b,确保a>b*/r=a%b;while(r!=0){a=b;b=r;/*实施"辗转相除"*/r=a%b;}printf("=%ld\n",b);/*输出求解结果*/}(2)求n个整数的最大公约数程序实现对于3个以上整数,最大公约数有以下性质:(a1,a2,a3)=((a1,a2),a3)(a1,a2,a3,a4)=((a1,a2,a3),a4),...应用这一性质,要求n个数的最大公约数,先求出前n-1个数的最大公约数b,再求第n个数与b的最大公约数；要求n-1个数的最大公约数,先求出前n-2个数的