What & How & Why

大话数据结构 笔记 第二章
我的笔记均包含大量个人理解内容，存在一定偏差。如果您发现错误，请留言提出，谢谢！

我们在第一章就说过程序设计的内容包括数据结构和算法。很显然，抛开算法谈数据就是耍流氓了。算法只有和对应的数据结构搭配，才能发挥出程序的最大功效。

算法就是描述解决问题的方法。算法（algorithm）这个词最早出现在波斯数学家阿勒.花刺子密在公元 825 年所写的《印度数字算术》中。如今普遍认可的算法定义是：算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每一条指令表示了一个或多个操作。

这句话信息量很大，包括了算法的诸多特性。我们接着来看算法的特性。

算法具有几个基本特性：

• 输入、输出：算法的输入个数大于等于零，而输出个数大于等于一。
• 有穷性：算法必须在有限的步骤内完成，并且每一步的步骤要在可接受的时间内完成。
• 确定性：算法的每一步步骤必须有确定的含义，不能有二义性。
• 可行性：算法的每一步都可以通过执行有限次数完成。

一个好的算法应该包括以下几个特性：

正确性：算法至少具有输入、输出和加工处理的无歧义性，能正确的反映需求，能正确的得到问题的答案。这又可以分为几个层次：

1. 语法正确。
2. 对合法输入的数据产生正确的结果。
3. 对非法的输入能产生满足规定的结果。
4. 算法对于精心选择（边界数据）等有满足要求的结果。

由此看来算法的正确性跟数学上的证明是有很大的关系的。不过对于我们来说，要验证一个算法对于所有输入的正确性是非常困难的，要通过严格的数学证明来解决。因此，应用中的算法以层次 3 为主。

好算法的另外一个特征是可读性。

可读性：算法设计的另一个目的是为了方便别的程序员阅读。可读性有助于别人理解算法。

一个好的算法还应该对输入数据不合法的情况做适合的处理。

最后，好的算法还需要具备时间消耗少，空间占用少的特点。

算法的时间效率是指对于同一个问题，执行时间越少的算法效率越高。而空间占用则指算法运行时对存储空间的占用，占用越低系统资源消耗越少。

算法效率的估算大致分两种方法：

• 事后统计
• 事前估算

都说实践出真知，对算法效率的测试，事后统计是一个很容易想到的办法：通过设计好的测试程序和数据，用计算机计时器对不同算法编制的程序的运行时间进行比较。但是这个办法存在很大的缺陷：

• 依赖测试程序，耗费额外的精力。
• 作为评判的标准之一时间受计算机软件、硬件的影响，可能会不精确。
• 算法设计的测试数据很困难，而且往往对影响时间关系不大。

事前估算的方法就是在计算机变之前，按照统计方法对算法进行估算。

一个程序的时间效率取决于以下几点：

• 算法采用的策略、方法。
• 编译产生的代码的质量。
• 问题的输入规模。
• 机器执行指令的速度。

第二条取决于编译器，第四条取决于硬件。由此可以看出，算法对程序的影响主要体现在两方面：算法的好坏，输入输出的规模。

算法的好坏直接体现在时间效率上，也就是运行多少次才能解决问题。而运行次数则跟输入输出的规模也有关系。因此我们我们在分析算法的时间的时候，需要把两个因素：基本操作的数量、输入的规模联系起来参考。我们来看看下图：


有没有发现其实运行时间跟消耗的操作次数其实是正比关系？而且我们也可以看到，对于这些不同的算法来说，$n$ 越大，算法体现出来的差异就越明显。

从书上的例子我们可以看到，只有当 $n$ 达到一定程度的时候，我们才能得知算法的优劣。因此，我们需要考察函数的渐进增长效率，也就是函数的自变量趋于无穷大的时候，算法的运行时间的增长。那么两个函数算法的优劣比较，其实也就为了算法时间增长率的比较。用数学定义来说就是：
给定两个函数$f(n)$、$g(n)$，存在一个整数$N$，使得对所有的 $n < N$，都有 $f(n) > g(n)$，那么我们称 $f(n)$的增长渐进快于$g(n)$，也就是$f(n)$的时间效率优于$g(n)$。