另一個 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)$（讀作“階 $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)$ 快。

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

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