第5章 贪心算法
5.1简介
例子： 有4种硬币，面值分别为2角5分、一角、五分和一分。现在要求以最少
的硬币个数找给顾客6角三分。
通常是：先拿两个2角5分的＋1个一角＋3个一分
这种找法所拿出的硬币个数最少。这种算法其实就是贪心算法。顾名思义：该算法
总是作出再当前看来最好的选择，并且不从整体上考虑最优问题，所作出的选择只是在
某种意义上的局部最优解。上面的解法得到的恰好也是最优解。因此，贪心方法的效率
往往是很高的。
假如，面值有一角一分、五分和一分，要找给顾客一角五分。如果还是使用上述贪
心算法，得到的解是：一个一角一分＋4个一分。而最优解是3个5分。
算然贪心算法不能对所有问题都能得到最优解，但是对很多问题（包括很多著名的
问题）都能产生整体最优解。例如，我们今天要讲的图的单元最短路径问题、最小生成
树问题。在有些情况下，算然不能得到整体最优解，但是结果确是最优解的很好近似。
使用贪心法的难点在于：证明所设计的算法确实能够正确解决所求解的问题。
5.2哈夫曼编码
哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在
20%～90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0，1串表
示各字符的最优表示方式。
给出现频率高的字符较短的编码，出现频率较低的字符以较长的编码，可以大大缩
短总码长。
前缀码
对每一个字符规定一个0,1串作为其代码，并要求任一字符的代码都不是其他字符
代码的前缀。这种编码称为前缀码。
编码的前缀性质可以使译码方法非常简单。
表示最优前缀码的二叉树总是一棵完全二叉树，即树中任一结点都有2个儿子结点。
平均码长定义为：使平均码长达到最小的前缀码编码方案称为给定编码字符集C的
最优前缀码。构造哈夫曼编码
哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码方案称为哈夫曼编码。
哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。
算法以|C|个叶结点开始，执行|C|－1次的“合并”运算后产生最终所要求的树T。
第一讲
第 1 页 第一章 算法分析技术
§1.1 算法及复杂性
算法从何入手，求解问题。计算机干什么？将所有想让计算机干的事全部描述成问题。
问题：什么是问题，怎么描述，日常生活中的问题描述，实际就是要让计算机干什么。输入，输出。
两个要素:输入输出，要有严格的描述。
实例：描述问题的所有参量。
询问：陈述问题所求的解的格式和解应满足的性质。
注意，计算机每次求解只是针对一个实例求解，问题的描述针对很多实例，通用的描述。
算法：对每个问题实例计算机都能计算出满足询问条件的正确答案，的计算方法。是一个过程，语句集合，语句有顺序，按照顺序执行语句，处理实例，得到正确答案。一种计算方法。对每个实例计算都能得到正确答案。
程序：算法的形式描述。
例子：求xn，求幂问题
实例(instance)：实数x和正整数n
询问(query)：xn=?
n=10，求：x10
每次计算x和n都不同，都是一个实例。
方法：算法， 第一讲
第 2 页 1 x*x*x*x*x*x*x*x*x*x
2 y=x*x, z=y*y, w=z*z, x10=y*w
3 [(x*x)2*x]2
方法1，2，3分别作9，4，4次乘法。考虑算法的总操作次数，*这个总操作次数称为算法的时间复杂度，或称为算法时间复杂性。
一个算法所需要的存储单元数目称为算法的空间复杂度，算法1，2，3的空间复杂度分别为2，4，2。
算法3的计算：两个变量，y=x*x；y=y*y；y=y*x；y=y*y。
时间复杂度和空间复杂度，不能太精确，没法太精确。因为相同的方法，两个人编出不同程序，同一个人两个时刻也编出不同程序。肯定不会完全相同。给出一个数量级来表达，数量级的参数是什么。
算法3推广到一般如何：想一种通用的办法。
1 begin
/n的m位2进制数为bm-1bm-2…b1b0
2 y=x
3 for i=m-2 down to 0 do
4 begin
不规则三角网（TIN）生成的算法
第五章 不规则三角网（TIN）生成的算法
在第四章，基于三角网和格网的建模方法使用较多，被认为是两种基 本的建模方法。三角网被视为最基本的一种网络，它既可适应规则分布数 据，也可适应不规则分布数据，即可通过对三角网的内插生成规则格网网 络，也可根据三角网直接建立连续或光滑表面模型。在第四章中同时也介 绍了 Delaunay 三角网的基本概念及其产生原理，并将三角网构网算法归纳 为两大类：即静态三角网和动态三角网。由于增量式动态构网方法在形成 Delaunay 三角网的同时具有很高的计算效率而被普遍采用。本章主要介绍 静态方法中典型的三角网生长算法和动态方法中的数据点逐点插入算法； 同时，还将给出考虑地形特征线和其他约束线段的插入算法。而其他非 Delaunay 三角网算法如辐射扫描法 Radial Sweep Algorigthm（Mirante & Weingarten,
1982）等本文将不再介绍。
5.1 三角网生长法
5.1.1 递归生长法
递归生长算法的基本过程为如图 5.1.1 所示：
3 2
1
3 2
1
（a）形成第一个三角形 (b) 扩展生成第二个和第三个三角形 图
5.1.1 递归生长法构建 Delaunay 三角网
（1）在所有数据中取任意一点 1（一般从几何中心附近开始），查找
1
距离此点最近的点 2，相连后作为初始基线 1-2； （2）在初始基线右边应用 Delaunay 法则搜寻第三点 3，形成第一个
Delaunay 三角形； （3）并以此三角形的两条新边（2-3，3-1）作为新的初始基线； （4）重复步骤（2）和（3）直至所有数据点处理完毕。 该算法主要的工作是在大量数据点中搜寻给定基线符合要求的邻域 点。一种比较简单的搜索方法是通过计算三角形外接圆的圆心和半径来完 成对邻域点的搜索。为减少搜索时间，还可以预先将数据按 X 或 Y 坐标分 块并进行排序。使用外接圆的搜索方法限定了基线的待选邻域点，因而降 低了用于搜寻 Delaunay 三角网的计算时间。如果引入约束线段，则在确定 第三点时还要判断形成的三角形边是否与约束线段交叉。
第2章 算法的效率分析基础习题
1.
①按照下列函数的增长次数对它们进行排列（按照从低到高的顺序）。
(n2)！，105100lgn，2n2，430.00131nn，2lnn，3n，3n
②考虑下面的递归算法。
算法：Q(n)
//输入：正整数n
if n=1 return 1
else return Q(n1)+2*n1
a． 建立该函数值的递推关系并求解，以确定该算法计算的是什么。
b．建立该算法所做的乘法运算次数的递推关系并求解。
c． 建立该算法所做的加减运算次数的递推关系并求解。
2.对于如下每一对f(n)和g(n)，要么f(n)=O(g(n)),要么g(n)=O(f(n)),但不可能两者都成立，确定f(n)和g(n)在O渐进意义下的关系。
（1）()2fnnn,2()gnn （2）()logfnnnn,()gnnn
（3）()logfnnn,()gnn （4）2()2(log)fnn,()log1gnn
3.根据O的定义，证明O(f)·O(g)=O(f·g)。
4.计算如下递推关系：
（1）()3(1)15(1)8TnTnT （2）()(1)1(1)3TnTnnT
