算法设计与分析知识点

算法设计与分析知识点（共8篇）

篇1：算法设计与分析知识点

第一章 概述

算法的概念：算法是指解决问题的一种方法或过程，是由若干条指令组成的有穷序列。算法的特征：

可终止性：算法必须在有限时间内终止；

正确性：算法必须正确描述问题的求解过程；

可行性：算法必须是可实施的；

算法可以有0个或0个以上的输入；

算法必须有1个或1个以上的输出。

算法与程序的关系：

区别：程序可以不一定满足可终止性。但算法必须在有限时间内结束；

程序可以没有输出,而算法则必须有输出；

算法是面向问题求解的过程描述，程序则是算法的实现。

联系：程序是算法用某种程序设计语言的具体实现；

程序可以不满足算法的有限性性质。

算法描述方式：自然语言，流程图，伪代码，高级语言。

算法复杂性分析：

算法复杂性的高低体现运行该算法所需计算机资源（时间，空间）的多少。

算法复杂性度量：

期望反映算法本身性能，与环境无关。

理论上不能用算法在机器上真正的运行开销作为标准（硬件性能、代码质量影响）。

一般是针对问题选择基本运算和基本存储单位，用算法针对基本运算与基本存储单位的开销作为标准。

算法复杂性C依赖于问题规模N、算法输入I和算法本身A。即C=F(N, I, A)。

第二章递归与分治

分治法的基本思想：

求解问题算法的复杂性一般都与问题规模相关，问题规模越小越容易处理。

分治法的基本思想是，将一个难以直接解决的大问题，分解为规模较小的相同子问题，直至这些子问题容易直接求解，并且可以利用这些子问题的解求出原问题的解。各个击破，分而治之。

分治法产生的子问题一般是原问题的较小模式，这就为使用递归技术提供了方便。递归是分治法中最常用的技术。

使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想，它几乎总是比子问题规模不等的做法要好。

分治法所能解决的问题一般具有以下几个特征：

该问题的规模缩小到一定的程度就可以容易地解决；

该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；利用该问题分解出的子问题的解可以合并为该问题的解；

该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。（这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好。）

递归的概念：

直接或间接地调用自身的算法称为递归算法，用函数自身给出定义的函数称为递归函数。

反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。

边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。

第三章动态规划

动态规划的基本思想：

动态规划算法与分治法类似，其思想把求解的问题分成许多阶段或多个子问题，然后按顺序求解各子问题。最后一个阶段或子问题的解就是初始问题的解。

分治法求解时，子问题数目太多，从而导致解决原问题需要耗费指数级时间。与分治法不同的是，动态规划中分解得到的子问题往往不是互相独立的。

但不同子问题的数目常常只有多项式级。用分治法求解时，有些子问题被重复计算了许多次。

动态规划的适用条件：

动态规划法解所能解决的问题一般具有以下两个基本因素：

一、最优子结构性质

当问题的最优解包含着其子问题的最优解时，称该问题具有最优子结构性质。

二、重叠子问题性质

递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。

其它同分治法。

动态规划问题的特征：

求解的问题是组合优化问题；

求解过程需要多步判断，从小到大依次求解；

子问题目标函数最优解之间存在依赖关系；

动态规划算法设计的基本步骤和要素：

基本步骤：

（1）找出最优解的性质，并刻画其结构特征。（考察是否适合采用动态规划法。）

（2）递归地定义最优值。(建立递归式或动态规划方程)

（3）以自底向上的方式（或以自顶向下的备忘录方法）计算出最优值。

（4）根据计算最优值时得到的信息，构造最优解。

要素：

最优子结构

重叠子问题

备忘录（表格）

应用实例分析：

1、矩阵连乘问题：

（1）分析最优解结构：

计算A[i:j]的最优次序所包含的计算矩阵子链 A[i:k]和A[k+1:j]的次序也是最优的。矩阵连乘计算次序问题的最优解包含着其子问题的最优解，满足最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。

（2）建立递归关系；

（3）计算最优值—递归求解（递归求解最优值复杂度较高的原因是：子问题重复度高)；计算最优值—迭代查表求解

计算最优值—备忘录求解

（4）构造最优解

第四章贪心法

贪心算法的基本思想：

当一个问题具有最优子结构性质时，可用动态规划方法求解，但有时会有更简单有效的方法。

顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。

贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。贪心算法中，较大子问题的解恰好包含了较小子问题的解作为子集，这与动态规划算法设计中的优化原则本质上是一致的。

动态规划算法在某一步决定优化函数的最大或最小值时，需要考虑到它的所有子问题的优化函数值，然后从中选出最优的结果；贪心算法的每步判断时，不考虑子问题的计算结果，而是根据当时情况采取“只顾眼前”的贪心策略决定取舍。

贪心算法的设计要素：

可以用贪心算法求解的问题一般具有2个重要的性质：

1、最优子结构性质：

当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征

2、贪心选择性质：

贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法与动态规划算法的主要区别。

动态规划算法通常以自底向上的方式求解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。

对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。

应用实例：

1、活动安排问题：

第五章回溯法

回溯法的基本思想：

回溯法的使用条件：

回溯法适用于搜索问题和优化问题。

回溯法的设计要素：

针对问题定义解空间：

问题解向量

解向量分量取值集合构造解空间树

两类典型的解空间树：

子集树：当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为子集树。子集树通常有2n个叶结点

排列树：当所给的问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。排列树通常有n!个叶结点。

判断问题是否满足多米诺性质。

搜索解空间树，确定剪枝函数。

确定存储搜索路径的数据结构。

第六章分支限界法

分支限界法的基本思想：

分支界限法类似与回溯法，也是在问题解空间中搜索问题解的一种算法。

分支界限法与回溯法思想对比：

求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。

搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。

在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。

此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。

常见的两种分支界限法：

队列式(FIFO)分支限界法：按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。

优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。

最大堆：最大效益优先

最小堆：最小耗费优先

篇2：算法设计与分析知识点

路由算法通常具有下列设计目标的一个或多个：

优化：

优化指路由算法选择最佳路径的能力，根据metric的值和权值来计算。例如有一种路由算法可能使用跳数和延迟，但可能延迟的权值要大些。当然，路由协议必须严格定义计算metric的算法。

简单、低耗：

路由算法也可以设计得尽量简单。换句话说，路由协议必须高效地提供其功能，尽量减少软件和应用的开销。当实现路由算法的软件必须运行在物理资源有限的计算机上时高效尤其重要。

健壮、稳定：

路由算法必须健壮，即在出现不正常或不可预见事件的情况下必须仍能正常处理，例如硬件故障、高负载和不正确的实现，

因为路由器位于网络的连接点，当它们失效时会产生重大的问题。最好的路由算法通常是那些经过了时间考验，证实在各种网络条件下都很稳定的算法。

快速聚合：

此外，路由算法必须能快速聚合，聚合是所有路由器对最佳路径达成一致的过程。当某网络事件使路径断掉或不可用时，路由器通过网络分发路由更新信息，促使最佳路径的重新计算，最终使所有路由器达成一致。聚合很慢的路由算法可能会产生路由环或网路中断。

在下图中的路由环中，某分组在时间t1到达路由器1，路由器1已经更新并知道到达目的的最佳路径是以路由器2为下一跳，于是就把该分组转发给路由器2.但是路由器2还没有更新，它认为最佳的下一跳是路由器1，于是把该分组发回给路由器1，结果分组在两个路由器间来回传递直到路由器2收到路由更新信息或分组超过了生存期。

灵活性

路由算法还应该是灵活的，即它们应该迅速、准确地适应各种网络环境。例如，假定某网段断掉了，当知道问题后，很多路由算法对通常使用该网段的路径将迅速选择次佳的路径。路由算法可以设计得可适应网络带宽、路由器队列大小和网络延迟。

篇3：算法设计与分析知识点

如何让学生理解这些概念,并能正确理解运用呢?算法概念的理解和数学模型的建立是解决这一核心问题的关键。基于此,笔者对本课进行了如下创新。

大胆构思,细心梳理。教师需要在合理构思的基础上进行可控的创新。基于此,我在教学中合理使用了“教学重难点前置”这一突破常规的方法。引入算法和自然语言描述的例子就是课后练习中带星号需要学生思考的例题。解决了这个例题问题,与之相关的算法、自然语言描述和数学建模问题会迎刃而解,使课堂产生高效益。

一站学习,高效实施。兴趣是激发学生学习欲望的内需,整个学习过程都基于学习网站。从推演算法入手,酝酿课堂的温度;从变量和重建数学模型入手,构建课堂的深度;从通过“微课”了解计算机语言的发展入手,营造课堂的广度。我从这三个维度精打细磨诸多课堂教学元素,构建高效的初中信息技术课堂。

教学目标分析

1.教学目标与教学重、难点

教学目标:(1)了解算法与变量的概念,学会建立数学模型。(2)初步了解计算机语言的发展。(3)通过解决具体生活问题,理解计算机处理问题的一般过程。(4)会用自然语言描述算法的过程。

教学重点:算法的概念。

教学难点:数学模型的建立。

2.教学思路

整个教学过程以理解与沟通为重心,围绕以下两个核心问题展开:一是生活中的“无刻度量杯取水”问题,通过此题进行算法、自然语言描述、变量、数学模型概念的梳理,实现知识的第一次重构。二是生活中的“数据交换”问题,引导学生通过引入第三个变量,理解重建数学模型,实现知识的第二次重构。

教学过程

1.创设情境,打造温度课堂

昨天,王老师在备课的时候遇到一个数学问题,我把题目带来了,请同学们帮忙告诉我解决这个问题的推算过程。

课件出示:用没有刻度的3毫升量杯和5毫升量杯,如何量出1毫升的水?

板书:A:3毫升B:5毫升结果Z:1毫升

想一想:杯子有几种操作方法(板书6种操作方法,如图1)。

设计意图:教学难点前置形成认知冲突,认知冲突能激发学生的学习兴趣,使学生产生学习的内驱力。

2.初识算法,经历探索过程

(1)初识算法

试一试:请同学们进入学习网站,在学习网站的“试一试”栏目中利用拖动“操作方法”模块的方式来尝试实现操作步骤(如图2)。

说一说(反馈):说说你的想法和操作过程。

利用学习网站中的排名记录,先展示步骤较多的操作算法,再展示步骤最少的操作算法(学生描述的同时,教师用图示进行板书)。

类似这样将解决问题的步骤清晰而完整地描述出来的过程,我们称之为算法。用日常生活中使用的语言来描述算法的步骤,则称之为自然语言描述,是算法描述常见的一种方法。

议一议(反馈):看到这两种操作算法,同学们有什么想说的吗?

结果相同,但操作算法相差较大,算法存在优劣,这个优劣将直接影响到执行的效率。

(2)认识变量

这样的题目,如果数值发生变化,操作算法也会出现相应的一些变化。

课件出示:用没有刻度的5毫升量杯和6毫升量杯,如何量出3毫升的水?

请完成刚才算法的同学尝试描述修改条件后的操作算法。

说一说:请一位同学说说想法和操作算法。

这些数值还可以改变吗?类似这样,这些可变数值的对象就是变量。(课件展示:变量是数据的存储单元,在程序执行过程中是可变的。)

生活中常见的变量有很多,你能说说吗?(长方形周长C=2(a+b);正方形周长C=4a)

类似这样用字母、数字及其他数学符号建立起来的描述解决问题的数学结构表达式,我们称之为数学模型。

设计意图:从生活实例切入,以解决问题为驱动,通过想一想、试一试、说一说等实践活动引导学生不断地对算法与变量两个概念进行多层面的理解与沟通。学生在活动中完成对相关知识的梳理与重构,积累“算法与程序”基本的活动经验。

3.提炼知识,挖掘知识深度

(1)交换数据

刚才,我们用自然语言描述的方法解决了“无刻度”量杯取水的问题。譬如生活中,服务员错误交换了盛牛奶和咖啡的杯子,又该用怎样的方法来完成杯子的交换呢?

读一读:请同学们先在学习网站“电子教材(教材pdf版,如图3)”中阅读学习,再说说你的想法。

说一说:阅读后,同学们有什么想说的吗?

梳理:当遇到异质液体时,就不能直接混合了,这时要分析问题,重新确定算法,需要引进第三个杯子Z (板书X、Y、Z)。对于怎样交换,我们需要重建数学模型,来进行数值交换操作。

(2)计算机语言的发展

刚才,我们知道算法可以用自然语言来描述。其实,算法不仅可用自然语言描述,还可以用程序语言来描述,如机器语言、汇编语言和高级语言。请同学们先在学习网站“微课在线”中观看学习。

说一说(反馈):请同学们说说对计算机语言又增加了哪些知识?可以通过小测试来试试自己学的情况哦。(学习网站小测试,图略。)

设计意图:学生的思维过程往往是从问题开始的。在解决核心问题的过程中,学生自然而然地对交换数据这个概念进行了梳理。同时,利用“微课”进行计算机语言发展的自学探究,使单位时间内的学习容量更大,使课堂教学效果最优化。

4.小结延伸

(1)梳理

根据“小测试”情况,梳理今天的学习情况。

对于今天所学的知识,建议同学们课后到“百度脑图”中进行笔记梳理。

(2)延伸

这就是刚才微课中展示的交换牛奶、咖啡过程的流程图(课件展示),也是下节课的学习内容,建议同学们课后去预习。

设计意图:注重信息技术与生活实际的联系,让学生学会梳理知识,提升能力,激发学生学习信息技术的兴趣。

篇4：算法设计与分析知识点

关键词：算法设计与分析课程；动态演示；WPF；C#

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2016）20-0078-02

Abstract： A learning software of algorithm design and analysis course is designed and implemented by using WPF and C# language under the environment of Visual Studio 2010. The bubble sort， the eight queen problem， the tower of Hanoi problem and the knapsack problem are chosen as demonstration of the greedy method， backtracking method， divide and conquer method and dynamic programming， trying to vividly display the demonstration process of above classical algorithms.

Key words： Algorithm design and analysis course； Dynamic demonstration； WPF； C#

算法演示程序是以圖形解释算法，动态演示能够帮助学生加深算法理解，在脑海中形成算法执行过程的直观生动的印象，进而提高算法的教学效果[1]。许多算法演示系统的设计与实现的思想都来源于M.Brown等制作的BLASA系统[2]，随着可视化技术的发展，算法演示程序能够更加生动地展现出求解问题的过程。一个良好的演示系统应当具有丰富的媒体表现力、深入的细节演示效果、灵活的交互能力以及适当的游戏功能四个特性[3]。

1 整体框架

本软件基于微软推出的用户界面框架WPF[4-5]，并在Visual Studio 2010平台下设计与开发的。它提供了可视化界面，用户可直观看到分治法、贪心法、动态规划法和回溯法四种经典算法策略的求解过程[6]，软件的整体框架如图1所示。

2 具体实现

2.1 分治法

本文选择了汉诺塔问题进行分治算法的演示。汉诺塔问题中，每个盘子在柱子上的运作方式与栈结构非常类似：只能移动最上面的盘子。程序中设置了三个栈用于模拟当前三个柱子的状态。

盘子在移动过程中只涉及了四个方向：向上出盘、向左或右边移动、向下入盘。程序设置了一个方向变量direction，出盘过程中，盘子在越过柱子顶部时始终保持了方向direction=0。进程在发现direction为0时会控制盘子一次向上移动一个单位，当盘子的下边界越过了柱子的上边界，direction改变，根据相应信息，将direction设置为向左或者向右方向，左右移动过程以及向下入盘过程的移动方式和判断方法和出盘过程类似，不再赘述。

2.2 贪心法

选取冒泡排序演示贪心算法。我们采用球来表示每一个待排元素[7]，并用其透明度表示元素值的大小。用户输入球体的数目和初试排列状态（程序提供了三种状态：随机排列、逆序排列、正序排列）后，系统内部动态分配等长的球体数组。这些元素都是实例化的对象，能够被添加到画布上。

利用WPF中的Double Animation动画类来实现，它通过指定一个double类型的初始值From和同类型的终值To，使被关联的控件形成动画。如：以下代码可实现Name为lblTest的控件在一秒钟的时间内宽度增加50的动态效果。同样，球体在画布中的位置也是属性，可用动画改变。

一般排序算法都分为两个基本操作：比较和交换。本软件的冒泡排序演示程序就是利用这两个基本操作来进行演示的。如图2所示，若无需交换，则给出提示文字；若需要交换，则利用动画将相应两个球的位置颠倒。

2.3 动态规划法

本文选择0-1背包问题演示动态规划法。具体演示过程：用户完成输入后，点击演示进入演示状态。程序采用单步演示的方式，用户单击按钮，程序演示一步。利用二维数组的列数代表背包的总重量，用户可以修改。程序中使用Grid控件模拟二维数组，Grid内部的Label控件需要动态生成，见如下代码。其中thingCount为物品总数，bagWeight为背包承重，lblC是用于方便访问指定单元格的Label而设置的Label类型数组。

动态规划求中间值的代码如下。其中，第005行的判断表示当前第i个物品的价值与前i-1个物品在背包承重为j-W_arr[i]时的最大价值之和，是否比前i-1个物品在背包承重为j时的最大价值高。

2.4 回溯法

本文选择8皇后问题演示回溯法，图3和4是8皇后问题的相关演示效果图。演示程序中有一个皇后放置的试探过程，如图3所示，黑色棋子表示当前已放好的皇后位置，红色的棋子表示正在试探中。若红色棋子试探成功，则将黑色棋子放在该位置。

在该程序的另一个功能中，用户可以自己放置棋子，来感受8皇后的探索过程。本程序提供了一个错误提示的小功能，若当前棋子与棋盘上某个棋子有冲突，即在同行同列或者同一对角线，那么就会有红线闪烁，表明无法放置，如图4所示。

3 结束语

本软件在设计过程中，参照良好算法演示系统的设计要求，提供了交互功能和图形演示跟踪的功能。在算法的教学过程中能让学生接触直观的操作演示，可更好地让学生知其所以然[8]，也更快地让学生具有利用计算机解决问题的思维方式。不足之处在于它不支持算法跟踪功能，无法从代码上深刻认识算法。

参考文献：

[1]Matthew MacDonald著， 王德才 译. WPF编程宝典——C#2010版[M].

[2]刘铁猛. 深入浅出WPF[M]. 北京： 水利电力出版社， 2010.

[3]陈慧南. 算法设计与分析——C++语言描述[M]. 2版.北京： 电子工业出版社， 2012.

[4]孙永新， 闫大顺. 动画演示与算法教学研究[J]. 现代计算机， 2009（10）： 81-83

[5]张文升， 周青云， 周晓聪. 算法演示系统研究与应用[J]. 计算机应用与软件， 2008， 10：41-43.

[6]李健. 汉诺塔算法演示系统的设计与实现[J]. 现代计算机， 2011（24）： 76-80.

[7]田军， 李丰军. 基于VB程序的冒泡排序算法演示[J]. 电脑知识与技术， 2011（36）： 9410-9412.

篇5：算法设计与分析学习心得

班级：物联网1201 姓名：刘潇 学号：1030612129

一、实验内容：

这学期的算法与设计课，老师布置了这四个问题，分别是货郎担问题，动态生成二维数组，对话框下拉列表，排序问题。

二、学习掌握：

基本程序描述：

（1）货郎担问题：货郎担问题属于易于描述但难于解决的著名难题之一，至今世界上还有不少人在研究它。货郎担问题要从图g的所有周游路线中求取具有最小成本的周游路线，而由始点出发的周游路线一共有（n一1）！条，即等于除始结点外的n一1个结点的排列数，因此货郎担问题是一个排列问题。货郎担的程序实现了利用穷举法解决货郎担问题，可以在城市个数和各地费用给定的情况下利用穷举法逐一计算出每一条路线的费用，并从中选出费用最小的路线。从而求出问题的解

（2）费用矩阵：费用矩阵的主要内容是动态生成二维数组。首先由键盘输入自然数，费用矩阵的元素由随机数产生，并取整，把生成的矩阵存放在二维数组中，最后把矩阵内容输出到文件和屏幕上。它采用分支界限法，分支限界法的基本思想是对包含具有约束条件的最优化问题的所有可行解的解（数目有限）空间进行搜索。该算法在具体执行时，把全部可行的解空间不断分割为越来越小的子集，并为每个子集内的解计算一个下界或上界。动态生成二维n*n的数组程序利用指针表示数组的行和列，并逐一分配空间，在输入n的数值后，系统自动分配空间，生成n*n的数组，并产生随机数填充数组，最后将结果输入到指定文件中。

（3）Mfc：在下拉列表框中添加内容程序，在下拉列表对应的函数中利用addstring添加需要的内容。首先定义下拉列表框为ccombox型，并定义其属性名，利用addstring函数可以任意添加需要的内容。a排序问题:快速排序的运行时间与划分是否对称有关，其最坏情况发生在划分过程中产生的两个区域分别包含n-1个元素和1个元素的时候。其算法的时间复杂度为O(n 2),在最好的情况下每次划分的基准恰好为中值，可得其算法时间复杂度为O(n㏒n)。算法的实现和理解和代码实现完全是两回事，想要完全掌握一种算法，需要动手实践，用代码实现，才能理解透彻，真正掌握。b对话框下拉列表：这个项目简单易懂，轻松实现。三.疑问与总结：

货郎担的问题，我认为穷举法相对比而言是比较初级的方法，费时耗力，适合在练习时选用，但是在实际问题中不建议采用。克鲁斯卡尔或者普里姆算法求取最小生成树的方法来解决货郎担的问题是更适合现实解决问题的。我认为程序可以用switch函数来将函数分成几个部分更人性化，比如分为解决问题的的选项，输出结果选项，退出程序选项等。再有就是费用矩阵的值可以从文件中读取，而结果也可以直接放在指定文件中，这样在实际应用中比较广泛。

动态生成二维数组的程序我认为如果按照规范性，我的方法是中规中矩的，毕竟再向下延伸，生成三维的数组，需要三层的指针来实现。但是就程序的简化程度和计算机处理时间来说，我认为这样双层指针的算法有些太占用内存，毕竟要给行和列各分配n个空间。我通过与同学的交流，我发现可以用1位数组来实现二维的n*n的数组。首先分配n*n的空间，然后通过循环在一行的数据达到n时自动换行。这样程序得到了一定的简化，并且减少了一定的内存使用。我认为这种方法是比较贴合实际的。

四.心得体会

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

篇6：算法设计与分析 实验指导书1

一、实验目的：

利用C/C++/JAVA等程序设计语言，实现本章节中分治算法、递归，汉诺塔问题/二分搜索算法/合并排序/快速排序等经典算法。通过本实验章节掌握递归、分治算法的设计思想及实现技巧，加深对课程知识的理解。

二、实验学时：2

三、实验任务：

利用高级程序设计语言，编程实现以下问题： 1）递归：排列问题，汉诺塔问题；

2）分治：递归实现的合并排序及非递归的自然合并排序；

四、实验要求

1，设计过程

理解课本中源代码或伪代码的思想，结合流程图等工具描述实验任务的设计过程，并独自完成代码编写、调试及测试过程。2，代码及注释

提交包含完整源代码及关键代码注释的实验报告。3，运行效果图及测试数据

实验报告中应有能体现源代码正确编译、运行的实验运行效果图及多组测试数据集。

4，心得体会

篇7：算法设计与分析知识点

1.课程基本信息

课程编号：

课程名称（中文）：算法设计与分析

课程名称（英文）：The design and analysis of algorithms 开课学期： 见培养方案与教学计划 课程类别： 专业基础课程

课程学时数与学分： 56学时（4学分，不含实验课时，4学时/周）

实验学时数与学分： 28学时（学分计算并入计算机科学实验课程，4学时/次/周）先修课程： 高等数学或数学分析，线性代数或高等代数，概率论与数理统计，离散数学，高级语言程序设计，数据结构

教学形式： 课堂讲授 + 课外教学 + 实验教学（实验课程实行单列）使用教材：

张德富，算法设计与分析，国防工业出版社，2009,8。教学参考书：

[1] T.H.Cormen, C.E.Leiserson, R.L.Rivest and C.Stein, Introduction to Algorithms(the second edition)，The MIT Press，2001 该书国内已引进，见《算法导论（第二版）》（影印版，中文本），高等教育出版社，2003 [2] M.H.Alsuwaiyel，Algorithms Design Techniques and Analysis，World Scientific Publishing Company，1998 M.H.Alsuwaiyel，吴伟昶 等译，《算法设计技巧与分析》（中文版），电子工业出版社，2004 [3] Sartaj Sahni著，汪诗林等译，《数据结构、算法与应用--C++语言描述》，机械工业出版社，2003 [4] 王晓东编著，《计算机算法设计与分析》，电子工业出版社，2005 [5] Gilles Brassard, Paul Bratley.《FUNDAMENTALS OF ALGORITHMICS》(算法基础)，清华大学出版社，2005 注：[1]和[2]两本书为主要教学参考书。

大纲制定者： 张德富、赵致琢、苏 畅（厦门大学计算机科学系）大纲审定者： 赵致琢（厦门大学计算机科学系）

2．课程性质、类别与任务

“算法设计与分析”是计算机科学与技术专业一门重点专业基础课程，也是学科核心专业基础课程之一，属于必修课程。本课程主要介绍算法的基础知识，包括抽象计算模型、算法基本概念、算法复杂性分析基础、算法设计的基本方法、以及算法复杂性理论基础。通过本课程的学习，要求学生理解并熟练掌握：了解可支持算法运行的抽象机器计算模型，算法的定义和复杂性概念，算法设计的基本技术方法，包括递归与分治法、贪心法、动态规划方法、回溯法、分支限界法以及高级图论算法等，理解并掌握算法复杂性的分析方法、NP完全性理论基础等计算复杂性的基本知识以及完全性证明概要。通过教学和实践，培养学生运用数学工具和方法分析问题和从算法的角度运用数学工具解决问题的基本能力，培养学生设计算法和分析算法复杂性的基本能力，训练学生的逻辑思维能力和想象力，从而使他们能够正确地分析和评价一个算法，进一步设计出真正有效或更有效的算法，并使之了解算法理论的基础知识和发展概况。在教学中，鼓励学生运用算法知识解决各个学科的实际计算问题，培养学生初步的独立开展科研工作的能力和理论联系实践，解决实际问题的能力，同时，为后续课程以及将来的研究工作提供必要的算法设计与分析的基础。

此外，配合实验课程的教学，学生应理论联系实际，理论指导实践，通过规范地完成一系列算法设计实验进一步巩固所学的相关书本知识，在知识、能力、素质上得到进一步的提高。

3．课程教学的基本要求（教学内容和教学重点）

“算法设计与分析”内容的重点是各种常用的算法设计方法和复杂性分析方法，包括递归与分治法、贪心法、动态规划方法、回溯法、分支限界法，以及高级图论算法、时空复杂性的分析方法、NP完全性理论基础。课程教学的基本要求是通过教学活动，使每一个学生较好地掌握课程的主要内容，同时具备对实际问题应用所学知识设计出有效算法并编程实现这些算法的能力。课程的教学内容主要包括如下知识点，其中，属于重点的内容用黑体标示，今后教学改革拟增加的内容用“{„„}”标示，部分非重要内容用括弧标注为“一般了解”： 基本概念：问题;抽象计算模型；算法的概念；算法正确性;算法效率；问题下界 算法的评估：时间复杂性和空间复杂性分析；算法的最优、最差和平均效率；渐近复杂性符号和基本效率类型；非递归算法的数学分析；{概率分析（一般了解）；分摊分析（一般了解）；算法的经验分析；算法可视计算方法}； 递归：递归设计；递归算法转非递归算法；递归算法的设计实例；递归算法的数学分析，{三种求解递归方程的方法}；

分治法：分治法的基本思想；分治法设计的特点；分治法的时间复杂性；分治法的应用（大整数乘法和Strassen矩阵乘法；棋盘覆盖）； 基本的排序算法及其复杂性分析：插入排序；堆排序；快速排序；排序算法复杂度分析及其比较（此处的教学重点在于算法分析，透过算法分析从中深入了解算法的特性，进一步揭示设计更为有效的算法的思路和途径）； 动态规划方法：动态规划的基本要素（含最优性原理）；矩阵连乘问题；0/1背包问题；装配线的调度问题；最长公共子序列；

贪心算法：贪心算法的基本要素；背包问题；哈夫曼编码；活动选择问题；{贪心算法的理论基础（一般了解）}；

回溯法：回溯法的基本思想；装载问题；0/1背包问题；旅行商问题；批处理的作业调度问题；n皇后问题；子集合问题；回溯法的效率分析；

分支限界法（分支定界法）：分支限界算法的基本思想；装载问题；0/1背包问题；旅行商问题；批处理的作业调度问题；分支限界法的效率分析；

网络与高级图论算法：最短路径问题（Prim算法；Kruskal算法；Dijkstra算法；Warshall算法和Floyd算法）；最大流问题（Ford-Fulkerson标号算法等）；最小费用最大流问题（最小费用算法等）；{匹配问题及其求解算法}； 问题的复杂性：NP完全性理论基础（P类与NP类问题，NP完全性问题及其归约；NP完全性证明；典型的NP完全问题）；{ 如何求算法复杂性的下界（一般了解）}。

4．关于教学目标、教学内容的建议和教学过程中应该注意的事项

算法设计与分析是计算机科学的核心问题之一。由于计算机科学与技术的大多数研究都与算法紧密相关，因此，高起点的算法理论基础逐步成为了高素质计算机科学与技术专门人才应该具备的必要的理论修养。设计算法的目的是要解决大量实际问题，对于较复杂的问题要求能设计出有效的算法。大量的研究实践表明，一个问题求解质量和效率的高低，主要取决于算法设计的质量。因此，算法设计与分析的重点是掌握算法的概念和基础理论，运用数学工具分析问题，从计算方法的角度如何给出非数值计算问题的计算方法、采用算法设计的常用方法设计算法，掌握分析和估计算法复杂性的方法，并特别注意以下几点：

第一，在介绍算法的基本概念时，应该着重介绍计算模型、算法的概念、考察算法的角度和算法评估的标准、复杂性分析的方法以及算法研究的目标与实际问题的关系；

第二，在介绍一些数据结构已经学习过的排序算法时，不应过多强调算法设计，而应该重点结合算法分析技术，用分析的方法评价算法的优劣，从分析结果得到设计更优算法的启示。在介绍高级的数据结构时，重点应放在对数据结构的复杂性分析上；

第三，在介绍算法设计的基本方法（例如分治法、贪心法、动态规划方法、回溯法与分支限界法）时，应该通过对大量经典问题的算法设计与分析，使学生逐渐掌握算法设计与分析的技巧，并特别注意各种算法的比较分析。例如，递归与分治、贪心与动态规划、回溯与分支限界；

第四，在介绍NP完全性理论时，应该着重从问题的分类以及各类问题的性质、相互关系入手进行研究，揭示问题的本质，从而为算法的设计提供方法指导。另外，应该着重掌握问题的转化及NP完全性理论的有关证明思想；

第五，在介绍线性规划问题及其相应算法时，应该着重介绍该算法的应用；

第六，鼓励教师将自己的研究或最新算法设计与分析的思想，结合到教学过程之中，鼓励和帮助学生运用所学的知识去解决实际问题，掌握理论与实践相结合的思想方法。第七，鼓励教师结合学科范型（也称范式），将学科方法论的内容融入教学过程之中（对教师暂不作基本要求），以帮助学生建立与“算法设计与分析”课程内容相关的科学的思想方法。

5．课外教学要求

本课程的课外教学内容和形式主要由学生阅读经典教材，任课教师辅导、答疑、批改作业、实践环节等几部分构成。本课程要求学生在有时间的情况下，尽可能完成教材中所有的习题。学生应在任课教师的帮助下，认真听课，反复思考，大量完成作业，在学习中反复进行阅读、思考、做习题，通过阅读、思考、做习题、分析、联想、概括、归纳、总结等多种有效的方式方法，比较全面、准确地掌握课程的主要内容和教学重点。

任课教师（包括助教）每周安排1次辅导、答疑，每次2小时。每次辅导、答疑至少应有一位教师参加，一般不得合并执行。主讲教师应批改全班学生作业量的5%，参加辅导、答疑的次数不少于总次数的1/5，以掌握教学的效果，调控教学进度。

课程对学生作业的质量要求是：正确、简洁、规范。

要求做题正确，意味着学生必须掌握基本概念、基本原理、基本方法、基本技术等课程的基本知识，基本知识不掌握，就很难正确解答问题，这是对学生知识水平和解决问题能力的考核。要求做题简洁和规范，意味着在正确解题的情况下，不应该存在“拖泥带水”和“东拉西扯”的问题，书面表达简练、规范，与教材中例题求解的表述基本一致。这些，正反映出学生在这方面训练有素，这是对学生素质的考核。

6．课程的实验教学

实验课程将安排一些有代表性的上机实验单元与本课程相呼应，目的是通过实验让学生体会理论与实践高度统一的学科特点，进一步认识理论、抽象、算法设计等三个过程及其相互关系，形成对学科范型更深入的体会和认识。它要求学生从分析问题出发，利用所学的算法设计技术去解决某一实际问题。通过实验工作，借助程序设计语言，掌握运用数据结构、算法和程序解决一些实际问题的方法。

学生应按照理论联系实际，理论指导实践的要求，在实际操作中规范地完成各项实验。通过实验工作，借助程序设计语言，设计并实现算法，进一步掌握运用数学工具，分析问题，提出求解方法，设计算法，分析算法的复杂性，对算法进行科学的评价等方面得到严格的训练。

实验教学按照实验单元进行，一个实验单元完成后或相近内容的一组实验单元完成后，每一个学生要撰写和提交实验报告。任课教师应依据每一个学生的实验报告和完成实验的情况，在学期结束时给出学生该门课程的学术评语和成绩，并与四个学年所有实验课程评语一起，最终产生对学生的实践能力作出综合评定的学术评语与成绩。学术评语应着重从发展的眼光和视角，考察学生是否能够理论联系实际，理论指导实践，按照实验课程的教学要求，规范地完成实验单元，较好或基本掌握了实验教学的内容。

在实验课程单列之前，课程的实践环节拟安排28学时（实际执行7次共7*4=28学时），教学内容由大纲确定，实验课程单列之后，实验考核成绩单独计算，不计入课程考核成绩。各实验单元和内容如下：

实验单元一：用贪心法求解一个具体问题的实验（程序实现）； 实验单元二：用动态规划方法求解一个具体问题的实验（程序实现）； 实验单元二：用回溯法求解一个具体问题的实验（程序实现）； 实验单元四：用分支限界法求解一个具体问题的实验（程序实现）； 实验单元五：用高级图论算法求解一个具体问题的实验（程序实现）。

上述五个实验完成后，每个学生应提交二个实验报告。前三个实验完成后提交一个实验报告，后两个实验完成后，提交一个实验报告。

7．考核的方式方法

课程结束考核方式： 闭卷考试 课堂考试时间： 3小时（180分钟）

考试命题： 任课教师命题，教研室分管该课程的负责人和分管教学的系副主任审题； 课程考试的命题内容要从大纲的要求出发，围绕本课程的教学内容、知识点和教学要求，着重从知识、能力、素质三个方面对学生进行全面的考核，重点考核学生运用知识解决问题的能力，同时考察学生的综合素质。考核范围为除了最后一周教学的内容外，其他大纲确定的知识点都在考试范围之内，课程考试的试卷命题范围不得免除期中考试已经考过的内容。试卷中不少于85%的内容应来自课程重点内容的范围，不少于10%的内容应来自课程非重点内容的范围，要求学生全面复习，以达到系统掌握，全面考核的目的。试卷的题型要力戒避免文科标准化试卷的题型，避免出现简单概念问答题和简答题。试卷题目数量一般为5、6、7题，以优秀学生在全部会做的情况下正常书写速度能够在120分钟内完成为宜。试卷题目数量的减少与全面考核的目的并不矛盾。由于考核的范围是明确的，只要教师不透露题型和范围，学生就必须全面复习，这样，即使题目不覆盖某些教学内容，也不会影响实际的教学效果。

随堂监考授权： 主讲教师和助教

篇8：静态排序算法设计与分析

关键词：静态排序,算法复杂度,记录比较,记录移动

0 引 言

随着各行各业的飞速发展,计算机需要存储与处理的数据也在以惊人的速度增加。在如此庞大的数据群中,人们为了便于检索,通常希望能在计算机中保存的数据是按关键字值大小排列的有序表。在现今的计算机系统中,有相当大的一部分CPU时间开销是用于对数据的排序整理上的,而在这一部分CPU时间开销中,记录移动所引起的CPU时间开销又占据了相当大的一部分,并且如果待排序的记录相当大(即每个记录所占空间较多)时,记录移动所引起的CPU时间开销将对整个数据排序的CPU时间开销起到决定性的作用。因此,学习和研究各种排序算法,分析并设计出高效适用的排序算法,是摆在计算机科学工作者面前的重要课题之一。为了解决大量的记录移动而引起的CPU时间开销问题,本文提出了静态排序算法。这是一种记录移动次数(2n)恒定的稳定的内部排序算法。

1 算法的定义与核心思想

1.1 定 义

静态排序算法是一种通过对数组Value[1…n]中任意两个记录比较来计算出每个记录在已排序数组中的索引值并把其储存在数组Index[1…n]中,进而由Result[Index [i]]=Value[i]直接得到已排序数组Result[1…n]以达到对数据排序的目的稳定的内部排序算法。

1.2 核心思想

每个记录在已排序数组中的索引值与其所在的数组中比它本身大(小)的记录的个数有关。具体而言,若在一个数组中小于记录A的记录有k(0<=k<n-1)个,则当对该数组排序后所得到的数组中记录A的索引值一定为k(规定:若Value[i]== Value[j]且i<j则Value[i]< Value[j])。由原数组记录值及各个记录在已排序数组中的索引值直接构成有序数组。

2 算法的实现

2.1 排序实现

静态排序算法的实现过程主要分为三步。

第一步 通过记录值比较来求得各个记录在已排序数组中的索引值。求索引值的过程中有两种不同的情况。情况一:数组中任意两个记录的值大小都不相同,此时在数组中比记录A的值小的记录的个数则为记录A在已排序数组中的索引值。情况二:数组中至少存在两个记录的值相同,假设这两个值相同的记录分别为记录C和记录D,此时比记录C和记录D的值(假设记录D比记录C在原数组中的索引值大)小的记录的个数则不可能同时是记录C和记录D在已排序数组中的索引值。为了保持静态排序是稳定排序的特性,假设记录D的值要比记录C的值大。综合上述两种情况所述,若记录X的值小于比其索引值大的记录Y的值则记录Y在已排序数组中的索引值加1,否则记录X在已排序数组中的索引值加1。当对数组中任意两个记录进行比较后,就可以得到所有记录在已排序数组中的索引值。

第二步 由数组Value[1…n]与数组Index[1…n]直接构成有序数组。其中巧妙地应用了两个数组相同位置的对应关系,即Index[i]中存储的索引值恰巧是Value[i]在已排序数组中的索引值。因此,可以得出Result[Index[i]]=Value[i]。这是一个有序有目的地插入记录的过程。当遍历了整个数组Index[1…n]后,所有的记录就有序地插入到了结果数组中,最终得到有序数组Result [1…n]。

第三步 把结果数组Result [1…n]中的所有记录拷贝到原数组Value[1…n]中,最终实现原数组的排序目的。下面是用算法语言描述静态排序的过程。静态算法如算法1所示[1,2,3]。

2.2 测试结果

如图1所示:原先数组是一个无序数组,调用静态排序算法排序后得到一个有序的数组,从而验证了静态排序算法的正确性。

3 算法及测试结果的分析

表1是在测试静态排序算法过程中各变量值及存储值的变化情况(表中CC是记录的比较次数)。

从表1可得每一趟比较都会得出在数组中比该记录小的记录的个数,这个数值也正好是该记录在已排序数组中的索引值。分析静态排序的效率:

时间复杂度:

$Y={\displaystyle \sum _1^{n-1}i}=n(n-1)/2$

需进行n(n-1)/2次比较,且移动记录2n次。因此,总的时间复杂度为Ο(n2)。

空间复杂度:

需要借助一个长度为n的整型数组空间和一个原数组相同的数组空间。所以空间复杂度为О(n)。

4 各种算法的比较与分析

4.1 各种算法的平均复杂度

如表2所示,从时间复杂度上看,静态排序、起泡排序、插入排序、选择排序的平均时间复杂度均为Ο(n2),而希尔排序、快速排序和归并排序的平均时间复杂度均为Ο(nlog2n)。从空间复杂度上来看,起泡排序、插入排序、希尔排序、选择排序仅需一个存储空间,空间复杂度为О(1)。静态排序与归并排序都需要与n同级别的空间,空间复杂度为О(n)。而快速排序需要的空间与原数组中记录的顺序有关,需要(log2n,n)个存储空间,空间复杂度为О(n)。

4.2 各种算法的记录的比较次数与移动次数

4.2.1 根据记录比较与移动次数的理论值分析比较算法

各种算法的记录比较次数的理论值如表3所示。

各种算法的记录移动次数的理论值如表4所示。

4.2.2 根据记录比较与移动次数的实验值分析比较算法

以下四张图是根据1000次实验得到的数据绘制而成的。为了真实地模拟实际中的排序问题,每次的测试数据都由随机数构造而成。

图2是各种排序算法中记录移动次数的总体比较,从图中可以看出起泡排序的记录移动次数是最多的,且比其它的排序方法的移动次数要多很多,插入排序的移动次数次之。其余五种排序方法的移动次序要少很多。

图3是图2中其余五种排序算法的记录移动次数的详细比较图,从图中可以得出静态排序的移动次数是最少的,快速排序次之,接着是选择排序,然后是希尔排序,最后是归并排序。所以只从记录的移动次数来看,静态排序是最优的。

图4是各种算法中记录比较次数的总体比较图,从图中可以直观地发现静态排序、起泡排序、静态排序的比较次数是最多的,大约是n2/2,插入排序的移动次数次之,大约是n2/4。

图5是图4中其余三种排序算法中记录比较次数的详细比较图,从图中可以看出归并排序的比较次数是最小的,快速排序次之,再次是希尔排序。同时根据各种排序算法的比较次数曲线变化幅度可以得出快速排序和希尔排序的比较次数受记录初始顺序的影响较大,而归并排序的比较次数受到记录初始顺序的影响却很小。

4.3 各种算法的稳定性

根据排序算法稳定性的定义以及各种算法的核心思想及实现可得静态排序、插入排序、起泡排序、选择排序和归并排序是稳定的,而希尔排序与归并排序是不稳定的。

4.4 各种算法的简单性

从算法简单性看,静态排序、插入排序、选择排序和起泡排序是简单算法,而希尔排序、快速排序和归并排序是经过改进后的算法,因此是复杂算法。

5 结 语

数据排序所引起CPU时间开销主要由排序过程中的记录比较次数和移动次数决定。从待排序的记录个数n的大小看,n越小,采用简单排序方法越合适,n越大,采用改进的排序方法越合适。因为n越小,Ο(n2)同Ο(nlog2n)的差距越小,并且输入和调试简单算法比输入和调试改进算法要少用许多时间。 从记录本身信息量看,若记录本身信息量越大,则移动记录所花费的时间就越多,所以对记录的移动次数较多的算法不利。在这种情况下,移动次数越小的算法将越有优势,本文提出的静态排序算法也就是为了更好地适应这种情况而提出的。

起泡排序是最简单的排序算法,在各个算法中平均效率是最低的,但便于理解,适用于记录个数n较小的排序中。

选择排序是一种简单排序算法,它的比较次数非常大,但是移动次数相对较小,所以适用于记录个数n较小而记录本身信息量较大的排序中[5]。

插入排序也是一种简单排序算法,它的比较次数和移动次数都比较大,约为n2/4,适用于记录个数n较小的排序中[6]。

希尔排序中当n在某个特定的范围内时,所需的比较次数约为n1.3,移动次数约为3n1.3,适用于记录个数较大而记录本身信息量较小的排序中[7]。

快速排序的平均时间为klog2n,从平均时间性能而言,快速排序最佳[4],适用于记录个数n较大的排序中[8]。

归并排序的平均时间复杂度为Ο(nlog2n),空间复杂度为О(n),适用于记录个数n较大而记录信息量也较大的排序中[9]。

静态排序是一种稳定的简单排序算法,它的记录比较次数非常大,但移动次数却是所有算法中最小的,并且记录的比较次数和移动次数仅与记录个数n有关而与记录的初始顺序无关,因此适应于记录个数n较小而记录信息量非常大的排序中。

参考文献

[1]阿霍,霍普克劳夫特,乌尔曼.计算机算法的设计与分析[M].黄林鹏,王德俊,张仕,译.机械工业出版社,2007.

[2]科曼,等.算法导论[M].潘金贵,等译.机械工业出版社,2006.

[3]郑宗汉,郑晓明.算法设计与分析[M].电子工业出版社,2010.

[4]严蔚敏,吴伟民.数据结构[M].清华大学出版社,2010.

[5]张明亮,李兴良.选择排序的一种改进及分析[J].苏州科技学院学报,2007,24(2).

[6]李宝艳,马英红.排序算法研究[J].电脑知识与技术,2007,2(8).

[7]杨智明.希尔排序算法实现与分析[J].电脑编程技术与维护,2010(2).

[8]杨锋英,刘会超.改进的快速排序算法[J].科技广场,2010(1).