原地演算法

在電腦科學中，原地演算法（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）。

另見

• 原地和非原地演算法列表