原地算法

在计算机科学中，原地算法（in-place algorithm，也称就地算法）是不需要额外的数据结构就能变换输入数据的算法。不过，分配少量空间给部分辅助变量是被允许的。算法执行过程中，输入的数据往往会被输出结果覆盖。原地算法只能通过替换或交换元素的方式来修改原始的输入。不满足“原地”原则的算法也被称为非原地（not-in-place）算法或异地（out-of-place）算法。

原地有多种不同的含义。在其最严格的形式下，原地算法只允许占用固定大小的额外空间，其中包含了函数调用和指针占用的空间。然而，这种形式有很大的局限性，因为他要求指向长度为 $n$ 的数组只能使用 $O(\log n)$ 个比特位。而更通用的形式认为，原地意味着算法在更改输入内容时不需要额外的空间，但是可以在进行这些操作时使用少量的非固定大小的空间。通常，这部分空间复杂度为 $O(\log n)$ ，不过某些情况下任何满足 $O(n)$ 的复杂度也是允许的。注意空间复杂度在是否将索引长度纳入此额外空间方面也是有多种选择的。常见的考量是将索引的数量或需要的指针数量算到空间复杂度当中的。在这篇文章中，我们所指的整体空间复杂度（DSPACE）将指针长度考虑在内了。因此，分析对应的存储空间占用会比忽略索引、指针长度的方法多一个 $\log n$ 因子。

一个算法既可能会，也可能不会将输出算入其整体的空间占用中。这是由于原地算法通常会直接使用输出来覆盖输入，因此不需要额外的空间。当把输入写入到仅允许写入的内存或流当中时，只考虑算法执行过程中的空间开销可能更恰当一些。在诸如对数空间归约等理论应用上，更典型的做法往往是将输出占用忽略（在这些情况下，更重要的是输出为仅允许写入）。

举例

给定一个 $n$ 个元素的数组 a，假设我们想要得到一个所有元素逆序排列的数组来替换原数组。一种看似简单的方式是创建一个大小相同的数组，然后将输入 a 中的元素按照恰当的顺序复制到新数组中，最后删除 a。

 function reverse(a[0..n])
     allocate b[0..n]
     for i from 0 to n
         b[n - i] = a[i]
     return b

不幸地是，这将导致 $O(n)$ 的额外空间用于同时存储数组 a 和 b。并且，内存分配与释放往往是比较慢的操作。由于最终我们不再需要 a，我们可以直接通过原地算法，用其自身的逆序排列来覆盖原来的值。不论数组有多大，整体上仅仅需要常数（2）个整数用于存放两个辅助变量 i 和 tmp。

 function reverse-in-place(a[0..n])
     for i from 0 to floor(n/2)
         tmp := a[i]
         a[i] := a[n-i]
         a[n-i] := tmp

正如另一个的例子，许多排序算法都会原地重新排列数组的元素，包括：

这些算法只需要少数几个指针，所以它们的空间复杂度都是 $O(\log n)$ ^[1]。

快速排序的确直接在待排序数据上进行操作。然而快速排序却因为其分治策略，需要 $O(\log n)$ 个栈空间指针来管理子数组。这就导致快速排序需要 $O(\log ^{2}n)$ 的额外空间。虽然说这种非常量大小的空间占用严格意义上已经将快速排序排除在原地算法之列了，但是通常仍然认为它和其他只需要 $O(\log n)$ 个额外指针的算法也属于原地算法。

大部分的选择算法都是原地执行的，虽然其中一些在找到最终常量大小的结果的过程中会相当程度上改变输入数组中元素的顺序。

部分文本操作函数，比如修剪、逆转，可以通过原地执行实现。

计算复杂度

在计算复杂度理论中，原地算法的严格定义规定了所有算法的空间复杂度需要满足 $O(1)$ ，也就是 DSPACE(1) 类型。这种类型限制很大；它等同于正则语言^[2]。事实上，上面给出的所有例子都不满足其规定。

我们通常认为 L 类型的算法，也就是需要 $O(\log n)$ 额外空间的算法是原地算法。这种类型更符合实践中的定义，因为它允许使用 $n$ 个指针或索引量。不过这种拓展的定义仍然不包含快速排序算法，因为快速排序中存在递归调用。

通过 L 类型来定义原地算法存在一些有趣的含义。比如它意指存在一个（非常复杂的）原地算法来判断无向图^[3]中的两个顶点之间有无路径。这是一个需要使用诸如深度优先搜索（每个顶点对应一个是否已经访问的标志位）等典型算法的，需要 $O(n)$ 额外空间的问题。有些问题，譬如判断一个图是否是二分图或测试两个图是否有相同的连通分支等，L 类型定义会反过来催生出原地算法来。可以参考 SL 复杂度获取更多信息。

随机性的角色

在很多情况下，一个算法的空间需求可以在很大程度上借由随机化算法来削减。比如说，我们想知道一个具有 $n$ 个顶点的图中某两个顶点之间是否处于同一个连通元件中。虽然不存在已知的简单、决定性的原地算法可以使用，但如果我们简单地从其中一个顶点开始，然后通过随机漫步约 $20n^{3}$ 步之后，我们恰好在同一连通元件中遇到另一个给定顶点的概率就非常高了。类似地，在一些素性检验，比如米勒-拉宾素性检验中就存在一些简单的随机化原地算法。另外还有一些简单的原地随机化因式分解算法，比如 Pollard-Rho 算法。参考 RL 复杂度和 BPL 复杂度了解更多关于这种现象的讨论。

函数式编程

函数式编程语言通常不推荐或是不支持能够覆写数据的显式原地算法，因为这是一种函数调用过程的副作用。取而代之的是，函数式编程语言只允许构建新的数据（结构）。然而，优秀的函数式编程语言编译器往往可以检测到与现存对象高度类似的新对象被创建，且旧对象被抛弃，并将这个过程在底层优化成对既有数据的变换。

原则上是有可能小心地构建出不会修改数据（除非数据不再会被使用）的原地算法的，但是这在实践中非常罕见。参考纯函数数据结构（purely functional data structures）。

另见

原地和非原地算法列表

参考资料

^ 指针占用的比特大小是 $O(\log n)$ ，但在大多数排序应用中，可以认为指针大小是一个常量。
^ Liskiewicz, M.; Reischuk, R. The complexity world below logarithmic space. Proceedings of IEEE 9th Annual Conference on Structure in Complexity Theory (IEEE Comput. Soc. Press). ISBN 0-8186-5670-0. doi:10.1109/sct.1994.315816.
^ Reingold, Omer, Undirected connectivity in log-space, Journal of the ACM, 2008, 55 (4): 1–24, MR 2445014, S2CID 207168478, doi:10.1145/1391289.1391291

[1] 指针占用的比特大小是 $O(\log n)$ ，但在大多数排序应用中，可以认为指针大小是一个常量。

[2] Liskiewicz, M.; Reischuk, R. The complexity world below logarithmic space. Proceedings of IEEE 9th Annual Conference on Structure in Complexity Theory (IEEE Comput. Soc. Press). ISBN 0-8186-5670-0. doi:10.1109/sct.1994.315816.

[3] Reingold, Omer, Undirected connectivity in log-space, Journal of the ACM, 2008, 55 (4): 1–24, MR 2445014, S2CID 207168478, doi:10.1145/1391289.1391291

[1]

[2]

[3]