原地算法

在计算机科学中，一个原地算法（in-place algorithm，也称“就地算法”）是基本上不需要借助额外的数据结构就能对输入的数据进行变换的算法。不过，分配少量空间给部分辅助变量是被允许的。算法执行过程中，输入的数据往往会被输出结果覆盖。原地算法只能通过替换或交换元素的方式来修改原始的输入。不满足“原地”原则的算法也被称为非原地（not-in-place）算法或异地（out-of-place）算法。 原地有多种不同的含义。在其最严格的形式下，原地算法只允许占用固定大小的额外空间，其中包含了函数调用和指针占用的空间。然而，这种形式有很大的局限性，因为他要求指向长度为 的数组只能使用 个比特位。而更通用的形式认为，原地意味着算法在更改输入内容时不需要额外的空间，但是可以在进行这些操作时使用少量的非固定大小的空间。通常，这部分空间复杂度为 ，不过某些情况下任何满足 的复杂度也是允许的。注意空间复杂度在是否将索引长度纳入此额外空间方面也是有多种选择的。常见的考量是将索引的数量或需要的指针数量算到空间复杂度当中的。在这篇文章中，我们所指的整体空间复杂度（）将指针长度考虑在内了。因此，分析对应的存储空间占用会比忽略索引、指针长度的方法多一个 因子。 一个算法既可能会，也可能不会将输出算入其整体的空间占用中。这是由于原地算法通常会直接使用输出来覆盖输入，因此不需要额外的空间。当把输入写入到仅允许写入的内存或流当中时，只考虑算法执行过程中的空间开销可能更恰当一些。在诸如等理论应用上，更典型的做法往往是将输出占用忽略（在这些情况下，更重要的是输出为仅允许写入）。