算法分析与设计期末总结

算法分析与设计

学习总结

题目：算法分析与设计学习总结

学 院 信息科学与工程学院

专 业 2013级计算机应用技术 届 次 学生姓名 学 号 2013110657

二○一三年一月十五日

算法分析与设计学习总结

本学期通过学习算法分析与设计课程，了解到：算法是一系列解决问题的清晰指令，代表着用系统的方法描述解决问题的策略机制。算法能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂性和时间复杂度来衡量。算法可以使用自然语言、伪代码、流程图等多种不同的方法来描述。计算机系统中的操作系统、语言编译系统、数据库管理系统以及各种各样的计算机应用系统中的软件，都必须使用具体的算法来实现。算法设计与分析是计算机科学与技术的一个核心问题。

设计的算法要具有以下的

复习

一、简答题（每小题5分，选答2题，共10分）

1. 什么是算法？试说明算法设计分析过程的一般框架和主要步骤。 2. 简述非递归算法时间效率分析的通用方案。 3. 简述递归算法时间效率的通用方案。

4. 简述蛮力法、分治法、减治法，变治法、时空权衡、动态规划、贪婪技术、迭代改进八种算法设计技术中至少三种技术基本思想或原理。

二、分析题（每小题10分，共20分） 1. 考虑下面的算法。P52

算法 Mystery(n) //输入：非负整数n

S=0

for i ? 1 to n do

S ? S + i*i Return S

a. 该算法求的是什么？ b. 它的基本操作是什么？ c. 该基本操作执行了多少次？ d. 该算法的效率类型是什么？

2. 考虑下面的递归算法。P52

算法 Secret(A[0..n-1]) //输入：包含n个实数的数组A[0..n-1] minval ? A[0]; maxval ? A[0] for i ?1 to n-1 do if A[i] < minval minval ? A[i] if A[i] > maxval maxval ? A[i] re

复习

一、简答题（每小题5分，选答2题，共10分）

1. 什么是算法？试说明算法设计分析过程的一般框架和主要步骤。 2. 简述非递归算法时间效率分析的通用方案。 3. 简述递归算法时间效率的通用方案。

4. 简述蛮力法、分治法、减治法，变治法、时空权衡、动态规划、贪婪技术、迭代改进八种算法设计技术中至少三种技术基本思想或原理。

二、分析题（每小题10分，共20分） 1. 考虑下面的算法。P52

算法 Mystery(n) //输入：非负整数n

S=0

for i ? 1 to n do

S ? S + i*i Return S

a. 该算法求的是什么？ b. 它的基本操作是什么？ c. 该基本操作执行了多少次？ d. 该算法的效率类型是什么？

2. 考虑下面的递归算法。P52

算法 Secret(A[0..n-1]) //输入：包含n个实数的数组A[0..n-1] minval ? A[0]; maxval ? A[0] for i ?1 to n-1 do if A[i] < minval minval ? A[i] if A[i] > maxval maxval ? A[i] re

大学算法分析与设计复习总结

第1章 绪论 考点：

1、算法的5个重要特性。（P3）

答：输入、输出、有穷性、确定性、可行性

2、 描述算法的四种方法分别是什么，有什么优缺点。（P4） 答：

1.自然语言 优点：容易理解；缺点：容易出现二义性，并且算法都很冗长。 2.流程图 优点：直观易懂；缺点：严密性不如程序语言，灵活性不如自然语言。 3.程序设计语言 优点：用程序语言描述的算法能由计算机直接执行；缺点：抽象性差，是算法设计者拘泥于描述算法的具体细节，忽略了“好”算法和正确逻辑的重要性，此外，还要求算法设计者掌握程序设计语言及其编程技巧。 4.伪代码 优点：表达能力强，抽象性强，容易理解

3、了解非递归算法的时间复杂性分析。(P13)

要点：对非递归算法时间复杂性的分析，关键是建立一个代表算法运行时间的求和表达式，然后用渐进符号表示这个求和表达式。 非递归算法分析的一般步骤是：

（1）决定用哪个（或哪些）参数作为算法问题规模的度量。 （2）找出算法的基本语句。

（3）检查基本语句的执行次数是否只依赖问题规模。 （4）建立基本语句执行次数的求和表达式。 （5）用渐进符号表示这个求和表达式。

[例1.4]：求数组最小值算法 in

大学算法分析与设计复习总结

第1章 绪论 考点：

1、算法的5个重要特性。（P3）

答：输入、输出、有穷性、确定性、可行性

2、 描述算法的四种方法分别是什么，有什么优缺点。（P4） 答：

1.自然语言 优点：容易理解；缺点：容易出现二义性，并且算法都很冗长。 2.流程图 优点：直观易懂；缺点：严密性不如程序语言，灵活性不如自然语言。 3.程序设计语言 优点：用程序语言描述的算法能由计算机直接执行；缺点：抽象性差，是算法设计者拘泥于描述算法的具体细节，忽略了“好”算法和正确逻辑的重要性，此外，还要求算法设计者掌握程序设计语言及其编程技巧。 4.伪代码 优点：表达能力强，抽象性强，容易理解

3、了解非递归算法的时间复杂性分析。(P13)

要点：对非递归算法时间复杂性的分析，关键是建立一个代表算法运行时间的求和表达式，然后用渐进符号表示这个求和表达式。 非递归算法分析的一般步骤是：

（1）决定用哪个（或哪些）参数作为算法问题规模的度量。 （2）找出算法的基本语句。

（3）检查基本语句的执行次数是否只依赖问题规模。 （4）建立基本语句执行次数的求和表达式。 （5）用渐进符号表示这个求和表达式。

[例1.4]：求数组最小值算法 in

算法设计与分析期末考试复习题

1． 算法有哪些特点？为什么说一个具备了所有特征的算法，不一定就是使用的算法?

2． 证明下面的关系成立：(参考例题1.5--1.6)

（1）logn!=Θ(nlogn) (2)2n=Θ(2n+1)

(3)n!= Θ(nn) (4)5n2-6n=Θ(n2)

1

3.考虑下面的算法：

输入：n个元素的数组A

输出：按递增顺序排序的数组A

1. void sort(int A[],int n) 2. { 3. int i,j,temp; 4. for(i=0;i

（1） 什么时候算法所执行的元素赋值的次数最少？最少多少次？

（2） 什么时候算法所执行的元素赋值的次数最多？最多多少次？

4.考虑下面的算法：

输入：n个元素的数组A

输出：按递增顺序排序的数组A

1. void bubblesort(int A[],int n) 2. { 3. int j,i,sorted; 4. i=sorted=0; 5. while(ii;j--)

算法设计与分析期末考试复习题

1． 算法有哪些特点？为什么说一个具备了所有特征的算法，不一定就是使用的算法?

2． 证明下面的关系成立：(参考例题1.5--1.6)

（1）logn!=Θ(nlogn) (2)2n=Θ(2n+1)

(3)n!= Θ(nn) (4)5n2-6n=Θ(n2)

1

3.考虑下面的算法：

输入：n个元素的数组A

输出：按递增顺序排序的数组A

1. void sort(int A[],int n) 2. { 3. int i,j,temp; 4. for(i=0;i

（1） 什么时候算法所执行的元素赋值的次数最少？最少多少次？

（2） 什么时候算法所执行的元素赋值的次数最多？最多多少次？

4.考虑下面的算法：

输入：n个元素的数组A

输出：按递增顺序排序的数组A

1. void bubblesort(int A[],int n) 2. { 3. int j,i,sorted; 4. i=sorted=0; 5. while(ii;j--)

第1章 绪 论

算法理论研究的是算法的设计技术和算法的分析技术，前者是指面对一个问题，如何设计一个有效的算法，后者则是对已设计的算法，如何评价或判断其优劣。二者是相互依存的，设计出的算法需要检验和评价，对算法的分析反过来又将改进算法的设计。

1.1 算法的基本概念

算法的概念在计算机科学领域几乎无处不在，在各种计算机软件系统的实现中，算法设计往往处于核心地位。例如，操作系统是现代计算机系统中不可缺少的系统软件，操作系统的各个任务都是一个单独的问题，每个问题由操作系统中的一个子程序根据特定的算法来实现。用什么方法来设计算法，如何判定一个算法的优劣，所设计的算法需要占用多少时间资源和空间资源，在实现一个软件系统时，都是必须予以解决的重要问题。

1.1.1 为什么要学习算法

用计算机求解任何问题都离不开程序设计，而程序设计的核心是算法设计。一般来说，对程序设计的研究可以分为四个层次：算法、方法学、语言和工具，其中算法研究位于最高层次。算法对程序设计的指导可以延续几年甚至几十年，它不依赖于方法学、语言和工具的发展与变化。例如，用于数据存储和检索的Hash算法产生于20世纪50年代，用于排序的快速排序算法发明于20世纪60年代，但他们至今仍被人

一 填空题

1. 一个计算机算法的指令序列需要满足性质的是输入、输出、确定性、有限性。

输入、输出、确定性、有限性

2.9n?10n的渐近表达式是 O(n)

22

3 . 下面程序段的时间复杂度是 O(n)

for (i=0; i

for (j=0; j

4．求两个n阶矩形的乘法C=A*B,其算法如下：

#define MAX 100

voidmaxtrixmult( int n, float a[MAX][MAX], float c[MAX][MAX]) { int i, j, k; float x; for( i=1; i<=n; i++)8 { for( j=1; j<=n; j++)

{ x=0;

for( k=1; k<=n; k++) x+=a[i][k]*b[k][j];

c[i][j]=x;

}

}

} 该算法的时间复杂度为 O(n)

5．通常用来表示时间算法的有以下六种多项式：

3

2

6．快速排序算法是基于分治策略的一个算法。其基本思想是，对于输入的子数组a[p:r],按以下3个步骤进行排序： 分解、递归求解、合并。

7. 合并排序算法的基本思想是 将待排序的元素分成大小大致相等的2个子集合，分别对两个子集合排序，最终将排好序的子集合合并成为所要求的集合。

华南农业大学期末考试试卷（A卷）

2004学年第二学期(2005.6) 考试科目： 算法设计与分析 考试类型：（开卷） 考试时间： 120 分钟

学号 姓名 年级专业 题号 得分 评阅人 一 二 三 四 总分 一、选择题（30分，每题2分）

1、一个算法应该包含如下几条性质，除了 A 。

（A）二义性 （B）有限性 （C） 正确性

（D）可终止性

2、解决一个问题通常有多种方法。若说一个算法“有效”是指 D 。 （A）这个算法能在一定的时间和空间资源限制内将问题解决 （B）这个算法能在人的反应时间内将问题解决 （C）这个算法比其他已知算法都更快地将问题解决 （D）A和C

3、当输入规模为n时，算法增长率最小的是 B 。 （A）5n （B）20log2n （C）2n2 （D）3nlog3n

4、渐进算法分析是指 B 。

（A）算法在最佳情况、最差情况和平均情况下的代价

（B）当规模逐步往极限方向增大时，对算法资源开销“增长率”上的简化分析 （C）数据结构所占用的空间

（D）在最