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