第2章 基础知识
Tracey：我不知道您在哪里。
Zoe：隐身术就是这样——您应该听说过的。
Tracey：我可不认为这属于基础知识。
——选自《Firefly》第14集台词
在我们将注意力转向本书主体内容，也就是那些数学技术、算法设计原则及经典算法之前，还必须先了解一些最基本的技术与原则。因为当您阅读到后续章节时，至少应该非常清楚类似“无反向环路的加权有向图”以及“Θ(n lg n)运行时间”这些词句所表达的具体含义。同时，我们也理应要对Python中一些基本数据结构的实现方式有个起码的了解。
幸运的是，这些基本问题并非都很难掌握。本章主要将聚焦于两个话题：首先是渐近记法（asymptotic notation），它主要关注的是运行时间的本质。再就是树（tree）与图（graph）这两种数据结构在Python中的实现方式。在这部分内容中，我们将为您介绍一些与程序运行时间有关的实用建议，以及应该如何避免一些基本的设计陷阱。不过，还是先让我们来看看应该如何在特定抽象机制中描述算法的行为吧。
2.1 计算领域中一些核心理念
20世纪30年代中期，英国数学家Alan Turing公开发表了一篇题为《On computable numbers, with an application to the Entscheidungsproblem》（其中译版为《论可计算数及其在判定问题上的应用》）的论文，这篇论文在许多方面都奠定了现代计算机科学的理论基础。如今，由他所提出的抽象设备——图灵机——已经成为了计算领域的理论核心。当然，这在很大程度上是因为该设备本身非常简单，而且容易掌握。图灵机是一种非常简单的抽象设备，它能读、能写，并且能沿着一条无限长的纸带移动。尽管图灵机有着各种不同的具体实现，但每种实现都可以被视为一台有限状态机：它由一个有限的状态集（包括已完成部分）与各种用于触发读写操作及不同状态切换的潜在符号共同组成。我们可以把它们看作这些机器运行所需要的一组规则（例如，“当我们在状态4的情况下遇到X，就向左移动一步，然后写入一个Y，并切换到状态9。”）。尽管这些机器看上去非常简单，但已经很让人惊叹了。因为有了它们，人们在计算领域就几乎无所不能了。
通常来说，所谓算法，实际上指的是一个执行过程，包含了能够解决某个特定问题的有限步骤集（其中可能包含了一些循环和条件元素）。而图灵机则是这个待解决问题的一种正规描述形式。这种形式通常被用于讨论解决该问题所需要的时间（这里既可以指整体时间，也可以指可接受的时间，相关内容将在第11章中详细讨论）。然而对于更细粒度上的算法效率分析来说，图灵机恐怕就不再是我们的首选了，因为这时候相较于可滚动的纸带，我们更需要的是一大块可直接存取的内存。于是随机存取机就应运而生了。
尽管随机存取机这种描述形式使用起来会有点儿复杂，但其实我们只需知道其能力极限在哪里，不至于让它影响我们的算法分析结果就可以了。简而言之，该机器是从标准单处理器计算机简化出来的一种抽象模型，它应该具备以下几个属性。
- 该机器上不会有任何形式的并发执行，它只有在执行完一条指令后才能执行其他指令。
- 该机器上的所有标准基本操作，如算术运算、比较运算以及内存存取，所耗费的时间都是常数级的（尽管具体数值上会有所不同），同时它也没有更复杂的基本操作，例如排序。
- 尽管计算机字（即word，其大小通常等于我们在常数时间内所能读取的值）的字长是有限的，但必须足够大，大到能满足我们在解决问题过程中所有的内存编址的需求，此外还要加上一定比例的额外变量。
当然，在某些情况下，我们可能还会有一些更具体的要求，但就机器本身而言也就大致如此了。
现在，相信我们已经对算法是什么，以及运行它们的抽象硬件环境有了一点直观的认知。下面我们来谈谈整个概念拼图中的最后一块：问题。就我们的目标而言，问题其实指的是输入与输出之间所存在的某种关系。事实上，我们还可以说得更精确一些：这里所反映的是一组集合对之间的关系（数学意义上的）——在这里，对于输入来说，什么样的输出是可接受的——并且借由指定这种关系的过程，我们的问题就会被确定下来。以排序问题为例，我们可以将其视为A、B两个集合之间的关系。这两个集合分别由一组序列组成。除了描述具体的排序过程外（该过程就是算法），我们还需要指定对于一个给定的输入序列（集合A中的某个元素），什么样的输出序列（集合B中元素）是可接受的。我们可以规定结果序列必须由输入序列相同的元素组成，并且将以递增顺序排列（其中的每个元素始终大于或等于前一个元素）。在这里，集合A中的元素（输入序列）就被我们称为问题实例。由此可见，关系本身实际上就是我们的问题。
当然，想要让我们的机器有的放矢，我们还得对其输入进行0、1编码。尽管在这里，我们无须去关心那些编码的具体细节，但是其中的理念很重要，因为其运行时间复杂度（这正是下一节中所要介绍的）是基于知道了问题实例大小，这个大小可以简单看成编码它所需的内存大小。我们会发现，这通常与编码自身的确切属性没有太大关系。