原地算法

在計算機科學中，原地算法（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)$。

快速排序的確直接在待排序數據上進行操作。然而快速排序卻因為其分治策略，需要 $O(\log n)$ 個棧空間指針來管理子數組。這就導致快速排序需要 $O(\log ^{2}n)$ 的額外空間。雖然說這種非常量大小的空間占用嚴格意義上已經將快速排序排除在原地算法之列了，但是通常仍然認為它和其他只需要 $O(\log n)$ 個額外指針的算法也屬於原地算法。

大部分的選擇算法都是原地執行的，雖然其中一些在找到最終常量大小的結果的過程中會相當程度上改變輸入數組中元素的順序。

部分文本操作函數，比如修剪、逆轉，可以通過原地執行實現。

計算複雜度

在計算複雜度理論中，原地算法的嚴格定義規定了所有算法的空間複雜度需要滿足 $O(1)$，也就是 DSPACE(1) 類型。這種類型限制很大；它等同於正則語言。事實上，上面給出的所有例子都不滿足其規定。

我們通常認為 L 類型的算法，也就是需要 $O(\log n)$ 額外空間的算法是原地算法。這種類型更符合實踐中的定義，因為它允許使用 $n$ 個指針或索引量。不過這種拓展的定義仍然不包含快速排序算法，因為快速排序中存在遞歸調用。

通過 L 類型來定義原地算法存在一些有趣的含義。比如它意指存在一個（非常複雜的）原地算法來判斷無向圖中的兩個頂點之間有無路徑。這是一個需要使用諸如深度優先搜索（每個頂點對應一個是否已經訪問的標誌位）等典型算法的，需要 $O(n)$ 額外空間的問題。有些問題，譬如判斷一個圖是否是二分圖或測試兩個圖是否有相同的連通分支等，L 類型定義會反過來催生出原地算法來。可以參考 SL 複雜度獲取更多信息。

隨機性的角色

在很多情況下，一個算法的空間需求可以在很大程度上藉由隨機化算法來削減。比如說，我們想知道一個具有 $n$ 個頂點的圖中某兩個頂點之間是否處於同一個連通元件中。雖然不存在已知的簡單、決定性的原地算法可以使用，但如果我們簡單地從其中一個頂點開始，然後通過隨機漫步約 $20n^{3}$ 步之後，我們恰好在同一連通元件中遇到另一個給定頂點的概率就非常高了。類似地，在一些素性檢驗，比如米勒-拉賓素性檢驗中就存在一些簡單的隨機化原地算法。另外還有一些簡單的原地隨機化因式分解算法，比如 Pollard-Rho 算法。參考 RL 複雜度和 BPL 複雜度了解更多關於這種現象的討論。

函數式編程

函數式編程語言通常不推薦或是不支持能夠覆寫數據的顯式原地算法，因為這是一種函數調用過程的副作用。取而代之的是，函數式編程語言只允許構建新的數據（結構）。然而，優秀的函數式編程語言編譯器往往可以檢測到與現存對象高度類似的新對象被創建，且舊對象被拋棄，並將這個過程在底層優化成對既有數據的變換。

原則上是有可能小心地構建出不會修改數據（除非數據不再會被使用）的原地算法的，但是這在實踐中非常罕見。參考純函數數據結構（purely functional data structures）。

另見

• 原地和非原地算法列表