另一個 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)$ 比${\mathcal {O}}(n^{2})$ 快，等等。