5

我在 Real World Haskell 上遇到了以下句子：

懒惰的评估有一些令人毛骨悚然的效果。假设我们要找到未排序列表的 k 个最小值元素。在传统语言中，显而易见的方法是对列表进行排序并获取前 k 个元素，但这很昂贵。为了提高效率，我们将改为编写一个特殊函数，一次性获取这些值，并且它必须执行一些中等复杂的簿记。在 Haskell 中，sort-then-take 方法实际上执行得很好：惰性确保列表只会被排序到足以找到 k 个最小元素。

他们为此提供了代码实现：

minima k xs = take k (sort xs)

但是是这样吗？我认为即使在 Haskell 中，它也应该做一个完整的列表来取出k元素。（想象一下在列表末尾有最小的数字）。我在这里错过了什么吗？

4

1 回答 1

1

（只是把我的评论放在这里回答）遍历整个列表并不等同于对其进行排序。假设进行快速排序，您围绕枢轴对列表进行分区，然后递归地对列表的左半部分和右半部分进行排序。如果您只要求左半部分的元素，则无需对右半部分进行排序。该参数可以递归应用。因此，如果您在排序后从长度列表中获取k元素，则复杂性是而不是。正如@MoFu 所指出的，Heinrich在这里有一篇很好的博文。nO(n + klog k)O(n log n)

于 2013-10-10T04:45:46.907 回答