Can you summarize the following document?
        
  假設我們想要將擁有"n"個專案的陣列反過來。一個最簡單作這件事的方式是這樣:  不幸地,這樣需要O("n")的空間來建立"b"陣列,且配置記憶體通常是一件緩慢的運算。如果我們不再需要"a",我們可使用這個原地演算法,用它自己反轉的內容來覆蓋掉:  在其他的例子,有數個排序演算法會原地重新排放陣列內容成為排序過的順序,包含:  快速排序通常被描述為一個原地演算法,但是事實上並不是。大部分的實作需要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)或測試兩個圖形使否有相同數量的連通分支,接著針對這些問題產出原地演算法。參考SL有更多的資訊。

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

  函式程式設計(functional programming)語言經常不鼓勵或不支援會覆蓋資料的原地演算法,因為這是副作用的一種型態;反之,他們只允許建立新的資料。然而,好的函式語言編譯器(compiler)在當一個與已存在之非常相似的物件被建立時,都經常會辨識出來,然後舊的就會被丟棄掉,而且會最把這最佳化為一個簡單的"引擎蓋之下"轉換。  基本上,有可能小心地建構原地演算法而不會更動資料(除非資料已不會再被使用),但是在實際上這卻很少見到。參考純函式資料結構(purely functional data structure)。

  Maciej Liśkiewicz and Rüdiger Reischuk. The Complexity World below Logarithmic Space. "Structure in Complexity Theory Conference", pp.64-78. 1994. Omer Reingold. Undirected ST-connectivity in Log-Space. Electronic Colloquium on Computational Complexity. No. 94.

  1. Liśkiewicz and Reischuk, pg.3, Theorem 2.
在電腦科學中,一個原地演算法(in-place algorithm)基本上不需要額外輔助的資料結構,然而,允許少量額外的輔助變數來轉換資料的演算法。當演算法執行時,輸入的資料通常會被要輸出的部分覆蓋掉。不是原地演算法有時候稱為非原地(not-in-place)或不得其所(out-of-place)。