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