延迟计算和时间复杂度
延迟计算和时间复杂度
我在stackOverflow上查看了非平凡的惰性求值，这让我找到了Keegan McAllister的演示：为什么要学习Haskell。在第8页中，他展示了最小函数，定义为：
minimum = head . sort
并且声称它的复杂度是O（n）。我不明白为什么说复杂度是线性的，如果通过替换排序是O(nlog n)。在帖子中提到的排序不能是线性的，因为它不假定任何有关数据的事情，这对于线性排序方法如计数排序是必需的。
惰性求值在这里起到了神秘的作用吗？如果是这样，背后的解释是什么？
admin 更改状态以发布 2023年5月22日
假设minimum\' :: (Ord a) => [a] -> (a, [a])是一个函数，它返回一个列表中最小的元素以及移除该元素后的列表。显然，这可以在O(n)的时间内完成。如果你定义sort，如下所示:\n\n
sort :: (Ord a) => [a] -> [a]
sort xs = xmin:(sort xs')
where
(xmin, xs') = minimum' xs
\n\n那么惰性求值意味着在(head . sort) xs中，只有第一个元素被计算。你可以看到，这个元素只是(pair中的) minimum\' xs的第一个元素，这可以在O(n)的时间内计算。\n\n当然，正如delnan指出的那样，复杂度取决于sort的实现方式。