第1章 算法与程序设计简介

算法分析与设计王宇160273615tlms327@163.com2013年2月25日课程安排：第1章算法与程序设计简介第2章穷举与回溯第3章递归与分治第4章递推第5章贪心算法第6章动态规划

第7章模拟第8章智能优化第9章并行算法简介实验安排：穷举与回溯算法实验递归算法实验分治算法实验递推算法实验贪心算法实验动态规划实验实验要求：实验报告：1、程序说明。说明程序的功能、结构。2、调试说明。包括上机调试的情况、上机调试步骤、调试所遇到的问题是如何解决的，并对调试过程中的问题进行分析，对执行结果进行分析。3、写出源程序和执行结果。第1章算法与程序设计概述主要内容：1.1算法与算法描述

算法定义算法描述1.2算法复杂性分析时间复杂度空间复杂度1.3程序设计简介算法与程序结构化程序设计1.1算法与算法描述1.1.1

算法算法是程序设计的基础，是计算机科学的核心。算法是指解决某一问题的运算序列。或者说算法是问题求解过程的运算描述，一个算法由有限条可完全机械地执行的、有确定结果的指令组成。3.

算法是满足下列特性的指令序列：

(1)确定性组成算法的每条指令是清晰的，无歧义的。

(2)可行性算法中的运算是能够实现的基本运算，每一种运算可在有限的时间内完成。

(3)有穷性算法中每一条指令的执行次数有限，执行每条指令的时间有限。(对任何的合法输入，算法总能在运算有限步后终止)

(4)输入一个算法有零个或多个输入。

(5)输出一个算法至少产生一个量作为输出。

算法的生成步骤设计确认分析编码检查调试计时算法的学习内容如何设计算法如何表示算法如何确认算法算法确认：一旦设计出了算法，就应证明它对所有可能的合法输入都能算出正确的答案，这一工作称为~

程序证明：证明程序对所有可能的合法输入都能得到正确的结果，这一工作称为~如何分析算法如何测试程序调试调试：在抽象数据集上执行程序，以确定是否会产生错误结果。作时空分布图：4.

选择算法的标准

通常求解一个问题可能会有多种算法可供选择，选择的主要标准是算法的正确性和可靠性。其次是算法所需要的存储空间少和执行时间短等。在实际工程中我们遇到许多高难度计算问题，有的问题在巨型计算机上用普通算法来求解可能要数个月的时间，而且很难找到精确解。但用一个好的算法，即使在普通的个人电脑上，可能只需数秒钟就可以求得解答。1.1.2

算法描述1.

描述算法的方式

算法是问题的程序化解决方案。一个问题可以设计不同的算法来求解，同一个算法可以采用不同的形式来表述。描述算法可以有多种方式，如自然语言方式、流程图方式、伪代码方式、计算机语言表示方式与表格方式等。当一个算法使用计算机程序设计语言描述时，就是程序。

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);

算法复杂性是算法运行时所需的计算机资源的量的高低体现运行该算法所需计算机资源的多少。算法的复杂性越高，所需的计算机资源越多；反之，算法的复杂性越低，所需的计算机资源越少。计算机资源，最重要的是时间资源与空间资源。需要计算机时间资源的量称为时间复杂度，需要计算机空间资源的量称为空间复杂度。算法分析是指对算法的执行时间与所需空间的估算，定量给出运行算法所需的时间数量级与空间数量级。

1.2算法复杂性分析

在分析算法时，隐藏细节的数学表示法成为大写O记法一个算法的时间复杂度是指算法运行所需的时间。一个算法的运行时间取决于算法所需执行的语句（运算）的多少。算法的时间复杂度通常用该算法执行的总的语句（运算）的数量级决定。就算法分析而言，一条语句的数量级即执行它的频数，一个算法的数量级是指它所有语句执行频数之和。

1.2.1时间复杂度时间复杂度定义

算法的计算时间f（n）定义：对于一个数量级为的算法，如果存在两个正常数c和m，对所有的n≥m，有

称当n充分大时，f（n）有上界，且称g（n）为它的一个上界，记作。该算法具有的运行时间，是指当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()。

证明：设f(n)=3(n+1)2,g(n)=n2。那么有f(n)=O(g(n))4.

算法时间关系：常见多项式时间算法:常见指数时间算法:一般地，当n取值比较大时，在计算机上实现指数时间算法是不可能的，就是比时间复杂度高的多项式时间算法运行也很困难。

35.

两个定理定理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.2】估算下列程序段代表算法的时间复杂度。for(k=1;k<=n;k++)

for(j=1;j<=k;j++){ x=k+j; s=s+x;}【例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，尽管其时间数量级都是，系数缩小了也是一个算法改进的成果。

算法的空间复杂度是指算法运行的存储空间，是实现算法所需的内存空间的大小。一个程序运行所需的存储空间通常包括固定空间需求与可变空间需求两部分。固定空间需求包括程序代码、常量与结构变量等所占的空间。可变空间需求包括数组元素所占的空间与运行递归所需的系统栈空间等。二维或三维数组是空间复杂度高的主要因素之一。在算法设计时，为降低空间复杂度，要注意尽可能少用高维数组。

1.2.2

空间复杂度

1.2.1

算法与程序

1.

基本概念算法是程序设计的基础，是程序的核心。程序是某一算法用计算机程序设计语言的具体实现。具体来说，一个算法使用C语言描述，就是C程序。上机实践是检验算法与程序的标准。

1.2程序设计简介

2.程序的内容一个程序应包括对数据的描述与对运算操作的描述两个方面的内容。著名计算机科学家沃思(NikiklausWirth)就此提出一个公式：数据结构＋算法＝程序

(1.4)数据结构是对数据的描述，而算法是对运算操作的描述。1.4程序实现求两个整数a,b的最大公约数(a,b)的欧几里德算法(见例1.1)，并应用欧几里德算法求n个整数的最大公约数。解：在欧几里德算法描述基础上进行数据描述即为求整数的最大公约数的程序。(1)求两个整数的最大公约数程序实现设置算法中的相关变量a,b,c,r为长整型变量，即有3.程序设计举例/*求整数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个数的最大公约数b,再求第n-1个数与b的最大公约数；依此类推。因而，要求n个整数的最大公约数，需应用n-1次欧几里德算法。

为输入与输出方便，把n个整数设置成m数组，m数组与算法中的相关变量a,b,c,r设置为长整型变量，个数n与循环变量k设置为整型。即有/*求n个整数的最大公约数*/#include<stdio.h>voidmain(){int

k,n;longa,b,c,r,m[100];

printf("请输入整数个数n:");/*输入原始数据*/

scanf("%d",&n);

printf("请依次输入%d个整数:",n);

for(k=0;k<=n-1;k++) {printf("\n请输入第%d个整数：",k+1);scanf("%ld",&m[k]);}b=m[0];

for(k=1;k<=n-1;k++)/*控制应用n-1次欧几里德算法*/{a=m[k];

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",m[0]);/*输出求解结果*/

for(k=1;k<=n-1;k++)

printf(",%ld",m[k]);

printf(")=%ld\n",b);}

1.3.2结构化程序设计

1.几个概念不应该把面向对象与面向过程对立起来。在面向对象程序设计中仍然要用到面向过程的知识。面向过程程序设计通常由结构化程序设计实现。任何简单或复杂的算法都可以由顺序结构、选择结构和循环结构这三种基本结构组合而成。顺序结构、选择结构和循环结构被称为程序设计的三种基本结构，也是结构化程序设计必须采用的结构。

2.结构化程序设计的基本要点（1）自顶向下,逐步求精；（2）模块化设计；（3）结构化编码。自顶向下是指对设计求解的问题要有一个全面的理解，从问题的全局入手，把一个复杂问题分解成若干个相互独立的子问题。逐步求精是指程序设计的过程是一个渐进的过程。

模块化就是把大程序按照功能分为若干个较小的程序。一个程序是由一个主控模块和若干子模块组成的。主控模块用来完成某些公用操作及功能选择，而子模块用来完成某项特