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})$ 更快，等等。