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

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

算法就是描述解决问题的方法。算法（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)$。

而我们也可以发现，随着 $n$ 逐渐增大，算法中低次项的影响也越来越小（参考书上表格 2-8-2，2-8-3）。因此，当 $n$ 足够大的时候，无论是低次项，还是最高此项的前面的常数，都会越来越不重要。反过来，对于最高此项，伴随着$n$的增长，其结果也增长的非常快。因此我们可以看出来函数的最高次项是算法时间效率的主要评判标准。我们在之后的判定中也应该把注意力放在函数的最高次项上。

既然明白了算法的时间效率与什么有关，我们就可以用一个标记（notation）来表示算法的时间复杂度了。我们把用大写的 $O$ 来表示算法的复杂度，用 $T(n)$ 来表示算法语句执行的次数。因此我们可以给出算法复杂度的定义：

算法的时间复杂度记做 $T(n) = O(f(n))$。它表示随着问题规模 $n$ 的增大，算法执行的时间的增长率与函数本身相同。因此算法的时间复杂度也可以成为算法的渐进时间复杂度，简称时间复杂度。

我们知道算法复杂度跟函数的最高次项是相关的。因此我们可以对函数做以下的处理：

1. 使用 1 取代所有的加法常数。
2. 只保留最高次项。
3. 如果最高次项存在，且不是 1, 则去掉这个项想成的常数。

比如 $f(n) = 2n^2 + n + 1$ 的复杂度就是 $n^2$。
具体的的分析主要查看的是数学的知识。不同的方式还有不同的求法，比如迭代用级数算，递归用递归方程算等，这本书比较浅，就不赘述了。

常见的时间复杂度有：

• 常数阶：$O(1)$
• 线性阶：$O(n)$
• 对数阶：$O(logn)$
• 平方阶：$O(n^2)$
• 立方阶：$O(n^3)$
• 指数阶：$O(2^n)$

我们刚才说到的 $O$ 其实代表了算法的最坏时间复杂度，这是一种对算法性能的保证（最坏也就这样了）。而平均情况是很有意义的，因为它是期望的运行时间。不过现实中我们很难通过估算来计算平均复杂度，一般都是通过大量的数据来得出的。因此我们对算法复杂度的分析，默认指定的是最坏复杂度。

~~DISQUS~~