原地算法

在计算机科学中，一个原地算法（in-place algorithm）基本上不需要额外辅助的数据结构,然而,允许少量额外的辅助变量来转换数据的算法。当算法运行时，输入的数据通常会被要输出的部分覆盖掉。不是原地算法有时候称为非原地（not-in-place）或不得其所（out-of-place）。
一个算法有时候会错误地被称为原地算法，只因为它用它的输出数据会覆盖掉它的输入数据。事实上这条件既不充分（在快速排序案例中所展示的）也非必要；输出数据的空间可能是固定的，或如果以输出为流数据而言，也甚至是可能无法被数清楚的。另一方面来看，有时候要决定一个算法是不是原地，而数它的输出空间可能是比较可行的，像是底下的第一个的reverse示例；如此使得它更难去严格地定义原地算法。在理论上的应用像是log-space reduction，更是典型的总是忽略输出的空间（在这些状况，更重要的是输出为仅能写入）。

在计算上的复杂度

在计算复杂性理论中，原地算法包含使用O(1)空间复杂度的所有算法，DSPACE(1)类型。这个类型是非常有限的，它与正则语言相等。事实上，它甚至不包含上面所列的任何示例。
因为这个原因，我们也考虑在L的算法，这类型的问题需要O(log n)额外的空间，来成为原地。虽然这个似乎与我们先前的定义矛盾，但是我们必须认为在抽象的世界，输入的数据可以是任意巨大的。在一部真实的计算机，指针（pointer）仅需要一个小的固定数量空间，因为物理内存的数量是固定的，但是一般上一个大小为n的数列需要O(log n)比特来作为它的索引（index）。
结果是否意指快速排序是原地的？其实一点也不—技术上来说，它需要O(log² n)空间，因为它的O(log n)堆栈帧架（stack frames）每一个都含有一个固定数量的指针（每一个大小为O(log n)）。
辨别拥有L的原地算法拥有某些有趣的含意；举例来说，它意指存在一个（相当地复杂）原地算法，决定在一个无向图（undirected graph）中的任两个节点（nodes）之间是否存在一条路径（path），这是一个需要O(n)个额外的空间，使用典型的算法像是深度优先搜索(depth-first search)（每个节点有个走访的比特）的问题。有些问题像是决定一个图形是否为二分图（bipartite graph）或测试两个图形使否有相同数量的连通分支，接着针对这些问题产出原地算法。参考SL有更多的信息。

随意的角色

在很多情况，借由使用随机化算法（randomized algorithms），一个算法的空间需求可以被极度地裁减掉。举个示例，我们希望知道一个有n个顶点（vertices）的图形中的两个顶点是否位于图中同一个连接组件（connected component）。没有已知简单、决定性的（deterministic）、原地算法来决定这件事，但是如果我们简单地由一个顶点开始，且运行大约20n³步的随机走路（random walk），那我们会偶遇到其他顶点来提供它不是在同一个组件（component）中的机会是非常地高。类似地，对于质数测试（primality test）有简单的随机化原地算法像是米勒-拉宾检验，也有简单原地随机化整数分解算法像是Pollard's rho算法。参考RL和BPL有对这个现象更多的讨论。

在函数的程序设计

函数程序设计（functional programming）语言经常不鼓励或不支持会覆盖数据的原地算法，因为这是副作用的一种类型；反之，他们只允许创建新的数据。然而，好的函数语言编译器（compiler）在当一个与已存在之非常相似的对象被创建时，都经常会识别出来，然后旧的就会被丢弃掉，而且会最把这最优化为一个简单的"引擎盖之下"转换。
基本上，有可能小心地建构原地算法而不会更动数据（除非数据已不会再被使用），但是在实际上这却很少见到。参考纯函数数据结构（purely functional data structure）。

注释

1. Liśkiewicz and Reischuk, pg.3, Theorem 2.
 2. Reingold.