另一个 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})$ 等等。