计算机数据结构的知识点(11)

用的一种数据结构。树的结构本质上有递归的性质——每一个叶节点可以被一棵子树所替代，反之亦然。实际上，每一种递归的结构都可以被转化为（或等价于）树形结构。说到递归在北京大学的数据结构课程里面有个老师经常说“不懂递归就不算北大计算机系的学生”，这样看来足以从侧面说明书的结构的重要性。

1.3 算法和算法分析



Algorithms and Algorithm Analysis

1.3.1算法

所谓算法（Algorithm）是对问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。在CLRS中是这样给出算法的定义的：Informally, an algorithm is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output. An algorithm is thus a sequence of computational steps that transform the input into the output.

一个算法必须满足以下五个重要特性：

1．有穷性 对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即：算法中的每个步骤都能在有限时间内完成；

2．确定性 对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径；

3．可行性 算法中描述的操作都可以通过已经实现的基本操作运算有限次实现之；

4．有输入 作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中；

5．有输出 它是一组与输入有确定关系的量值，是算法进行信息加工后得到的结果。

1.3.2算法设计的原则

设计算法时我们应当严格考虑：

1．正确性（Correctness）

首先，算法应当满足以特定的“规格说明”方式给出的需求。对算法是否“正确”的理解可以有以下四个层次：

a．程序中不含语法错误；

b．程序对于几组输入数据能够得出满足要求的输出结果；

c．程序对于精心选择的、典型、苛刻的几组输入数据能够得出满足要求的结果；

d．程序对于一切合法的输入数据都能得出满足要求的结果；

通常以第c层意义的正确性作为衡量一个算法是否合格的标准。因为作为输入，我们有时候不可能提前做出所有的预期。


2. 可读性(Readability)

算法主要是为了人的阅读与交流，其次才是为计算机执行。因此算法应该易于人的理解；另一方面，晦涩难读的程序易于隐藏较多错误而难以调试；有些程序设计者总是把自己设计的算法写的只有自己才能看懂，这样的算法反而没有太大的价值。

3．