算法设计与分析课程总结

湖南理工学院课程论文

课程名称 数据结构与算法设计 姓 名 学 号

专业班级 年 级 2014级

学 院 计算机学院 日 期 2015年6月25日

课程论文评价标准

评价等级（分值） 指标 评价内容 A 选题 选题是否新颖；是否有意义；是否与本门课程相关。 论文题目 0-1背包问题的设计与实现

得分 B C D 5-0 20-16 15-11 10-6 思路是否清晰；逻辑是否严密；结构论证 是否严谨；研究方法是否得当；论证是否充分。 20-16 15-11 10-6 5-0 文献 文献资料是否翔实；是否具有代表性。 20-16 15-11 10-6 规范 能力 文字表达是否准确、流畅；是否符合学术道德规范。 是否运用了本门课程的有关理论知识；是否体现了科学研究能力。 20-16 15-11 10-6 20-16 15-11 10-6 总分： 5-0 5-0 5-0 评阅教师签名： 年

湖南理工学院课程论文

课程名称 数据结构与算法设计 姓 名 学 号

专业班级 年 级 2014级

学 院 计算机学院 日 期 2015年6月25日

课程论文评价标准

评价等级（分值） 指标 评价内容 A 选题 选题是否新颖；是否有意义；是否与本门课程相关。 论文题目 0-1背包问题的设计与实现

得分 B C D 5-0 20-16 15-11 10-6 思路是否清晰；逻辑是否严密；结构论证 是否严谨；研究方法是否得当；论证是否充分。 20-16 15-11 10-6 5-0 文献 文献资料是否翔实；是否具有代表性。 20-16 15-11 10-6 规范 能力 文字表达是否准确、流畅；是否符合学术道德规范。 是否运用了本门课程的有关理论知识；是否体现了科学研究能力。 20-16 15-11 10-6 20-16 15-11 10-6 总分： 5-0 5-0 5-0 评阅教师签名： 年

《算法设计与分析》课程上机指导

《算法设计与分析》上机指导1

实习内容

习题一（工程名为101、源程序名为101） 选择排序法的伪代码描述如下： 算法1.4 SelectionSort（参见Page 8） 输入：数组A[1..n]

输出：按升序排列的数组A[1..n]

1. for i←1 to n-1 2.

Selection(i)

3. end for 过程Selection(i)

1. k←i

2. for j←i+1 to n 3.

if A[j]

4. end for

5. if k≠i then 交换A[i]和A[k]

用C语言实现上述算法并上机通过。

// ******************************************************* // * 工 程 名：101.dsp * // * 程 序 名：101.cpp

*

// * 主要功能：选择排序法

*

// * 学号姓名：20112633226 张云龙 * // * 编制时间：

算法分析与设计

学习总结

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

学 院 信息科学与工程学院

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

二○一三年一月十五日

算法分析与设计学习总结

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

设计的算法要具有以下的

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

第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

华南农业大学期末考试试卷（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）在最

第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个子集合，分别对两个子集合排序，最终将排好序的子集合合并成为所要求的集合。

《算法设计与分析》课程的心得体会

以最少的成本、最快的速度、最好的质量开发出合适各种各样应用需求的软件，必须遵循软件工程的原则，设计出高效率的程序。一个高效的程序不仅需要编程技巧，更需要合理的数据组织和清晰高效的算法。这正是计算机科学领域里数据结构与算法设计所研究的主要内容。一些著名的计算机科学家认为，算法是一种创造性思维活动，并且处于计算机科学与技术学科的核心。

在计算机软件专业中算法分析与设计是一门非常重要的课程，很多人为它如痴如醉。很多问题的解决，程序的编写都要依赖它，在软件还是面向过程的阶段，就有程序=算法+数据结构这个公式。算法的学习对于培养一个人的逻辑思维能力是有极大帮助的，它可以培养我们养成思考分析问题，解决问题的能力。

如果一个算法有缺陷，或不适合某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂性和时间复杂度来衡量。算法可以使用自然语言、伪代码、流程图等多种不同的方法来描述。 计算机系统中的操作系统、语言编译系统、数据库管理系统以及各种各样的计算机应用系统中的软件，都必须使用具体的算法来实现。 算法设计与分析是计算机科学与技术的一个核心问题。因此，学习算法