6 算法设计与分析课程教学大纲
【适用专业】 计算机科学与技术
【课 时】 理论课时：32
【学 分】 2
【课程性质、目标和要求】
《算法设计与分析》是计算机科学与技术专业的专业课。无论是计算科学还是计算实践，算法都在其中扮演着重要角色。本课程的教学目的是讲授在计算机应用中常常遇到的实际问题的解法，讲授设计和分析各种算法的基本原理、方法和技术，培养学生对算法复杂性进行正确分析的能力。
课程基本要求是
⑴掌握算法分析的基本概念和理论。
⑵掌握算法设计技术和分析算法以及算法复杂性。
【教学时间安排】
本课程计 2 学分，理论课时32, 学时分配如下：
序号 课程内容/实验名称 实验类型 课时 备注
1 算法引论 理论课时2
2 递归与分治策略/分治法实验 理论课时4
3 动态规划/动态规划实验 理论课时5
4 贪心算法 理论课时3
5 回溯法 理论课时3
6 分支限界法 理论课时3
7 概率算法 理论课时3
8 NP完全性理论 理论课时3
9 近似算法 理论课时3
6 10 算法优化策略 理论课时3
合 计 理论课时32
【教学内容要点】
第一章 算法引论
一、学习目的要求
1．了解算法的计算复杂性分析方法
2．理解算法分析的基本理论
3．掌握算法分析的基本概念
二、主要教学内容
1. 算法的基本概念
2. 表达算法的抽象机制
3. 采用Java语言与自然语言相结合的方式描述算法的方法
4. 算法的计算复杂性分析方法
第二章 递归与分治策略
一、学习目的要求
1．理解典型范例中递归与分治策略应用技巧
2．掌握递归与分治策略
3．掌握数学归纳法证明算法正确性方法
二、主要教学内容
1. 递归的概念
2. 分治法的基本思想
3. 二分搜索技术
编写人：杨玉建
1 |
算法分析(第二章)：递归与分治法
一、递归的概念
知识再现：等比数列求和公式：
1、定义： 直接或间接地调用自身的算法称为递归算法。
用函数自身给出定义的函数称为递归函数。
2、与分治法的关系：
由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供
了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而
其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归
过程的产生。分治与递归经常同时应用在算法设计之中，并由此产生许多高效算
法。
3、递推方程：
(1)定义：设序列
01,....
naaa
简记为{
na
}，把
na
与某些个()
iain
联系起来的
等式叫做关于该序列的递推方程。
(2)求解：给定关于序列{
na
}的递推方程和若干初值，计算
na。
4、应用：阶乘函数、Fibonacci数列、Hanoi塔问题、插入排序
5、优缺点：
优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，
因此它为设计算法、调试程序带来很大方便。
缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空
间都比非递归算法要多。
二、递归算法改进：
1、迭代法：
(1)不断用递推方程的右部替代左部
(2)每一次替换，随着n的降低在和式中多出一项
(3)直到出现初值以后停止迭代
(4)将初值代入并对和式求和
(5)可用数学归纳法验证解的正确性
2、举例：
-----------Hanoi塔算法----------- ---------------插入排序算法-----------
()2(1)1
(1)1TnTn
T=−+
= ()(1)1WnWnn
W=−+−
（1）=0
编写人：杨玉建
2
|
2
1n-23()2(1)1
2[2(2)1]1
2(2)21
...
2++2...1
21nn
nTnTn
Tn
Tn
T−−=−+
=−++
=−++
=
=++
=−（1）2
()(1)1
计算机算法设计五⼤常⽤算法的分析及实例
摘要
算法（Algorithm）是指解题⽅案的准确⽽完整的描述，是⼀系列解决问题的清晰指令，算法代表着⽤系统的⽅法描述解决问题的策略机制。也就是说，能够对⼀定规范的输⼊，在有限时间内获得所要求的输出。如果⼀个算法有缺陷，或不适合于某个问题，执⾏这个算法将不会解决这个问题。不同的算法可能⽤不同的时间、空间或效率来完成同样的任务。
其中最常见的五中基本算法是递归与分治法、动态规划、贪⼼算法、回溯法、分⽀限界法。本⽂通过这种算法的分析以及实例的讲解，让读者对算法有更深刻的认识，同时对这五种算法有更清楚认识
关键词：算法，递归与分治法、动态规划、贪⼼算法、回溯法、分⽀限界法Abstract
Algorithm is the description to the problem solving scheme ,a set of clear instructions to solve the problem and represents thedescribe the strategy to solve the problem using the method of system mechanism . That is to say, given some confirmimport，the Algorithm will find result In a limited time。If an algorithm is defective or is not suitable for a certain job, it isinvalid to execute it. Different algorithms have different need of time or space, and it's efficiency are different.
There are most common algorithms: the recursive and divide and conquer、dynamic programming method、greedyalgorithm、backtracking、branch and bound method.According to analyze the five algorithms and explain examples, makereaders know more about algorithm , and understand the five algorithms more deeply.
计算机时代２０１２年第１期 ・ ２７ ・ 基于分治和递归策略的排序算法及实现 孙义欣 （潍坊工程职业学院继续教育学院，山东青州２６２５００） 摘要：对关键字数量远少于记录数量的排序问题进行了研究，提出了基于分治和递归策略的有效算法。经与选择排 序算法比较，该算法在各种情况下的交换次数均明显少于经典的选择排序算法。 关键词：排序；关键字；分治；递归 中图分类号：ＴＰ３１２ 文献标志码：Ａ 文章编号：１００６—８２２８（２０１２）０１—２７—０２ Ｓｏｒｔｉｎｇ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｄｉｖｉｄｅ—ａｎｄ－ｃｏｎｑｕｅｒ ｓｔｒａｔｅｇｙ ａｎｄ ｒｅｃｕｒｓｉｖｅ ｓｔｒａｔｅｇｙ ａｎｄ ｉｔｓ ｒｅａｌｉｚａｔｉｏｎ Ｓｕｎ Ｙｉｘｉｎ （Ｃｏｌｌｅｇｅ ｏｆ Ｆｕｒｔｈｅｒ Ｅｄｕｃａｔｉｏｎ，Ｗｅ扣ｎｇ Ｅｎｇｉｎｅｅｒｉｎｇ Ｖｏｃａｔｉｏｎａｌ Ｃｏｌｌｅｇｅ，Ｑｉｎｇｚｈｏｕ，Ｓｈａｎｄｏｎｇ ２６２５００，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｅ ｓｏｒｔｉｎｇ ｐｒｏｂｌｅｍ ｆｏｒ ｔｈｅ ｎｕｍｂｅｒ ｏｆ ｋｅｙｗｏｒｄｓ ｆａｒ ｌｅｓｓ ｔｈａｎ ｔｈａｔ ｏｆ ｒｅｃｏｒｄｓ ｉｓ ｒｅｓｅａｒｃｈｅｄ，ａｎｄ ａｎ ｅｆｆｅｃｔｉｖｅ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｄｉｖｉｄｅ—ａｎｄ—ｃｏｎｑｕｅｒ ａｎｄ ｒｅｃｕｒｓｉｖｅ ｓｔｒａｔｅｇｉｅｓ ｉｓ ｐｕｔ ｆｏｒｗａｒｄ．Ｃｏｍｐａｒｅｄ ｗｉｔｈ ｓｅｌｅｃｔｉｏｎ ｓｏｒｔｉｎｇ ａｌｇｏｒｉｔｈｍ，ｔｈｅ ｅｘｃｈａｎｇｉｎｇ ｆｒｅｑｕｅｎｃｙ ｏｆ ｔｈｉｓ ａｌｇｏｒｉｔｈｍ ｉｓ ｏｂｖｉｏｕｓｌｙ ｌｅｓｓ ｔｈａｎ ｔｈａｔ ｏｆ ｃｌａｓｓｉｃ ｓｅｌｅｃｔｉｏｎ ｓｏｒｔｉｎｇ ａｌｇｏｒｉｔｈｍ ｕｎｄｅｒ ｖａｒｉｏｕｓ ｃｉｒｃｕｍｓｔａｎｃｅｓ． Ｋｅｙ ｗｏｒｄｓ：ｓｏｒｔｉｎｇ；ｋｅｙｗｏｒｄ；ｄｉｖｉｄｅ ａｎｄ ｃｏｎｑｕｅｒ；ｒｅｃｕｒｓｉｏｎ ０引言 递归技术经常用在算法设计之中，并由此产生许多结构清 晰、可读性强的算法。一个函数、过程、概念或数据结构，如果 在其定义内部或说明内部直接或间接地出现其自身的引用，或 者是为了描述某一问题的状态，必须用到它的上一状态，而描 述上一状态又必须用到它的再上一状态……这种用自己来定 义自己的方法，称之为递归或者递归定义。在程序设计中，函 数直接或间接调用自己，就称为递归调用。若调用自己，称之 为直接递归。若函数Ｐ调用函数ｑ，而ｑ又调用Ｐ，则称之为问接 递归。要使用递归技术编程，首先要确定求解问题的递归模 型，然后再转换成对应的用某种语言编写的函数或过程。递归 模型反映了一个递归问题的递归结构。 以Ｆｉｂｏｎａｃｃｉ数列为例，它可以递归定义为： ｌ ｉｆ ｎ＝０ Ｆ（ｎ）＝ ｌ Ｆ（ｎ一１）＋Ｆ（ｎ一２） ｉｆ ｎ＞ｌ Ｆ（Ｏ） 和Ｆ（１）＝１给出了递归的终止条件，我们称为递归出 口；Ｆ（ｎ）＝Ｆ（ｎ—１）＋Ｆ（ｎ一２）给出了ＦＣｎ）与其前两项的关系，我们称 之为递归体。一般地，一个递归模型是由递归出口和递归体两 部分构成的，前者确定递归到何时结束，后者确定递归的方 式。递归设计是把一个不能或不好直接求解的“大问题”转化 为一个或几个“小问题”，再把这些“小问题”进一步分解为更小 的“小问题”来解决，即通过分解使问题的规模逐渐降低，直至 每个小问题都可以直接解决（此时分解到递归出口）。当然，递 归分解不是随意地分解，递归分解要保证“大问题”与“小问题” 规模不同但模型相似。 任何一个可以用计算机求解的问题所需的求解时间都与 其规模有关。问题的规模越小，解题所需的计算时间往往也越 少，从而也更加容易处理。但有时候要想直接解决一个较大的 问题，可能是比较困难的。分治法的设计思想是，将一个难以 直接解决的大问题，分割成一些规模较小的问题，分割出的各 个小问题与原问题类型相同但规模较小，这样便于各个处理， 分而治之。如果原问题可分割成ｋ个子问题，ｌ＜ｋ≤ｎ，且这些 子问题都可解，并可以利用这些子问题的解求出原问题的解， 那么这种分治法就是可行的。由分治法产生的子问题往往是 原问题的较小模式，这就为使用递归技术提供了方便。 １问题的提出 在实际问题中我们经常会遇到这样的情况，即要求排序的 记录的关键字数量相对于记录数来说是较少的。例如，要对某 次考试的考生按考试成绩排名，考试成绩按百分制，参加考试 的考生可能有几百人甚至上千人或更多，这种情况下记录关键 字的数量相对于记录数来说就非常有限。对于这种具有特殊 性质的记录进行排序，用原有的一些经典的排序算法实现效率 不一定高。对一些特殊问题的处理我们可以在经典排序算法 的基础上进行改进并实现。 ２算法分析 考虑到关键字的数量较少，而记录数较多的特殊情况，如
