原地算法

维基百科，自由的百科全书

原地算法正在校对翻译。
歡迎您積極參與校對與修訂，原文在en:in-place_algorithm。

在計算機科學中，一個原地算法（in-place algorithm）是一種使用小的，固定數量的額外之空間來轉換資料的算法。當算法執行時，輸入的資料通常會被要輸出的部份覆蓋掉。不是原地算法有時候稱為非原地（not-in-place）或不得其所（out-of-place。

一個算法有時候會不正當地被稱為原地算法，只因為它用它的輸出資料會覆蓋掉它的輸入資料。事實上這並不足夠（在快速排序案例中所展示的）或是它所必須的；輸出資料的空間可能是固定的，或如果以輸出為串流資料而言，也甚至是可能無法被數清楚的。另一方面來看，有時候要決定一個算法是不是原地，而數它的輸出空間可能是比較可行的，像是底下的第一個的 reverse 範例；如此使得它更難去嚴格地定義原地算法。在理論上的應用像是log-space reduction，更是典型的總是忽略輸出的空間（在這些狀況，更重要的是輸出為僅能寫入）。

[编辑] 範例

假設我們想要將擁有n個項目的陣列反過來。一個最簡單作這件事的方式是這樣：

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

不幸地，這樣需要O(n)的空間來建立b陣列，且配置記憶體通常是一件緩慢的運算。如果我們不在需要a，我們可使用這個原地算法，用它自己反轉的內容來覆蓋掉：

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

在其他的例子，有數個排序算法會原地重新排放陣列內容成為排序過的順序，包含：

冒泡排序
Comb sort
選擇排序
插入排序
堆排序
Smoothsort
希尔排序
Stupid sort

快速排序通常被描述為一個原地算法，但是事實上並不是。大部份的實作需要O(log n)的空間來支持它的分治法（divide-and-conquer）遞迴。

大部份選擇算法也是原地，雖然在找到最後結果的過程中，有某些相當地重新排列輸入陣列，但卻是固定大小的結果。

[编辑] 在計算上的複雜度

在計算複雜性理論中，原地算法包含使用O(1)空間複雜度的所有算法，DSPACE(1)類型。這個類型是非常有限的；它與正規語言¹相等。事實上，它甚至不包含上面所列的任何範例。

因為這個原因，我們也考慮在 L 的算法，這類型的問題需要O(log n)額外的空間，來成為原地。雖然這個似乎與我們先前的定義矛盾，但是我們必須認為在抽象的世界，輸入的資料可以是任意巨大的。在一部真實的電腦，指標（pointer）僅需要一個小的固定數量空間，因為實體記憶體的數量是固定的，但是一般上一個大小為n的數列需要O(log n)位元來作為它的索引（index）。

結果是否意指快速排序是原地的？其實一點也不 — 技術上來說，它需要O(log² n)空間，因為它的O(log n)堆疊框架（stack frames）每一個都含有一個固定數量的指標（每一個大小為O(log n)）。

辨別擁有 L 的原地算法擁有某些有趣的含意；舉例來說，它意指存在一個（相當地複雜）原地算法，決定在一個無向圖（undirected graph）中的任兩個節點（nodes）之間是否存在一條路徑（path），這是一個需要O(n)個額外的空間，使用典型的算法像是深度優先搜尋(depth-first search)（每個節點有個走訪的位元）的問題。有些問題像是決定一個圖形是否為二分圖（bipartite graph）或測試兩個圖形使否有相同數量的連結元件（connected component），接著針對這些問題產出原地算法。參考SL有更多的資訊。

[编辑] 隨意的角色

在很多情況，藉由使用隨機化算法（randomized algorithms），一個算法的空間需求可以被極度地裁減掉。舉個範例，我們希望知道一個有 n 個頂點（vertices）的圖形中的兩個頂點是否位於圖中同一個連接元件（connected component）。沒有已知簡單、決定性的（deterministic）、原地算法來決定這件事，但是如果我們簡單地由一個頂點開始，且執行大約20n³步的隨機走路（random walk），那我們會偶遇到其他頂點來提供它不是在同一個元件（component）中的機會是非常地高。類似地，對於質數測試（primality test）有簡單的隨機化原地算法像是米勒-拉宾检验，也有簡單原地隨機化整數分解算法像是Pollard's rho 算法。參考RL和BPL有對這個現象更多的討論。

[编辑] 在函數的程式設計

函數程式設計（functional programming）語言經常不鼓勵或不支援會覆蓋資料的原地算法，因為這是副作用的一種型態；反之，他們只允許建立新的資料。然而，好的函數語言編譯器（compiler）在當一個與以存在之非常相似的物件被建立時，都經常會辨識出來，然後舊的就會被丟棄掉，而且會最把這最佳化為一個簡單的"引擎蓋之下"轉換。

基本上，有可能小心地建構原地算法而部會更動資料（除非資料已不會再被使用），但是在實際上這卻很少見到。參考純函數資料結構（purely functional data structure）。