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