Haskell/演算法複雜度

複雜度理論研究的是程式執行時間與輸入大小之間的關係。有很多優秀的複雜度理論入門書籍，任何一本好的演算法書籍都會解釋基礎知識。我會盡量簡短地討論這裡的內容。

其目的是說明程式如何隨著更多資料的增加而擴充套件。如果你有一個在非常小的資料量上執行速度很快但在大量資料上卻卡住的程式，它就不是很有用（當然，除非你知道你只會處理少量資料）。考慮以下 Haskell 函式，用於返回列表中所有元素的總和

sum [] = 0
sum (x:xs) = x + sum xs

這個函式需要多長時間才能完成？這是一個非常難的問題；它將取決於各種因素：你的處理器速度、記憶體量、加法運算的具體方式、列表的長度、你的計算機上正在執行的其他程式等等。這太複雜了，所以我們需要發明一個更簡單的模型。我們使用的模型是一種任意“機器步長”。所以問題是“這個程式要完成需要多少個機器步長？”在這種情況下，它只取決於輸入列表的長度。

如果輸入列表的長度為 $0$，則該函式將需要 $0$ 或 $1$ 或 $2$ 個機器步長，具體取決於你如何計算它們（也許是 $1$ 步進行模式匹配，以及 $1$ 步返回 $0$ 的值）。如果列表長度為 $1$ 呢？好吧，它將需要與長度為 $0$ 的列表所需的時間相同，再加上幾個額外的步長來執行第一個（也是唯一一個）元素。

如果輸入列表的長度為 $n$，它將花費與空列表相同數量的步驟（將此值稱為 $y$），然後，對於每個元素，將花費一定數量的步驟來進行加法和遞迴呼叫（將此數字稱為 $x$）。然後，此函式的總執行時間為 $nx+y$，因為它需要進行 $n$ 次加法。這些 $x$ 和 $y$ 值稱為 *常數*，因為它們與 $n$ 無關，實際上只取決於我們如何定義機器步驟，所以我們真的不想認為它們很重要。因此，我們說這個 sum 函式的複雜度為 ${\mathcal {O}}(n)$（讀作“order $n$”）。基本上說某件事是 ${\mathcal {O}}(n)$ 意味著對於一些常數因子 $x$ 和 $y$，該函式需要 $nx+y$ 個機器步驟才能完成。

考慮以下列表排序演算法（通常稱為“插入排序”）

sort []  = []
sort [x] = [x]
sort (x:xs) = insert (sort xs)
    where insert [] = [x]
          insert (y:ys) | x <= y    = x : y : ys
                        | otherwise = y : insert ys

該演算法的工作原理如下：如果我們要對空列表或只有一個元素的列表進行排序，我們直接返回它們，因為它們已經排序了。否則，我們有一個形如 x:xs 的列表。在這種情況下，我們對 xs 進行排序，然後希望將 x 插入到適當的位置。這就是 insert 函式的作用。它遍歷現已排序的尾部，並將 x 插入到它自然適合的位置。

讓我們分析一下這個函式完成需要多長時間。假設對長度為 $n$ 的列表進行排序需要 $f(n)$ 步。那麼，為了對一個長度為 $n$ 的列表進行排序，我們首先需要對列表的尾部進行排序，這需要 $f(n-1)$ 時間。然後，我們需要將 `x` 插入到這個新的列表中。如果 `x` 需要放到最後，這將需要 ${\mathcal {O}}(n-1)={\mathcal {O}}(n)$ 步。把所有這些加起來，我們看到我們需要做 ${\mathcal {O}}(n)$ 數量的工作 ${\mathcal {O}}(n)$ 次，這意味著這個排序演算法的整體複雜度是 ${\mathcal {O}}(n^{2})$。在這裡，平方不是一個常數值，所以我們不能把它忽略掉。

這意味著什麼？簡單來說，對於非常長的列表，`sum` 函式不會花費很長時間，但是 `sort` 函式會花費相當長的時間。當然，有些演算法執行速度比簡單的 ${\mathcal {O}}(n^{2})$ 慢，也有一些演算法執行速度比 ${\mathcal {O}}(n)$ 快。（還要注意，一個 ${\mathcal {O}}(n^{2})$ 演算法在實踐中可能比一個 ${\mathcal {O}}(n)$ 演算法快得多，如果執行 ${\mathcal {O}}(n^{2})$ 演算法的單步操作所需時間短得多。）

考慮列表和陣列的隨機訪問功能。 在最壞的情況下，訪問長度為 $n$ 的列表中的任意元素將花費 ${\mathcal {O}}(n)$ 時間（想想訪問最後一個元素）。 但是對於陣列，您可以立即訪問任何元素，這被稱為 *常數* 時間，或 ${\mathcal {O}}(1)$，這基本上是任何演算法都能達到的最快速度。

複雜性理論還有很多內容，但這足以讓你理解本教程中所有討論。 只需記住 ${\mathcal {O}}(1)$ 比 ${\mathcal {O}}(n)$ 比 ${\mathcal {O}}(n^{2})$ 更快，等等。