哈斯克尔：头。在线性时间内合并排序（对于最小元素）？

Question

在 HaskellWiki https://wiki.haskell.org/Performance/Laziness中，他们将合并排序函数引入为非惰性函数

merge_sort []  = []
merge_sort [x] = [x]
merge_sort lst = let (e,o) = cleave lst 
              in merge (merge_sort e) (merge_sort o) where
 merge :: (Ord a) => [a] -> [a] -> [a]
 merge xs [] = xs
 merge [] ys = ys
 merge xs@(x:t) ys@(y:u)
     | x <= y    = x : merge t ys
     | otherwise = y : merge xs u

因为你首先必须递归地分割列表

 cleave = cleave' ([],[]) where
 cleave' (eacc,oacc) [] = (eacc,oacc)
 cleave' (eacc,oacc) [x] = (x:eacc,oacc)
 cleave' (eacc,oacc) (x:x':xs) = cleave' (x:eacc,x':oacc) xs

然后，向上减少层，合并它们。所以合并排序需要 n(log n) 时间运行。但组成

min xs = head . merge_sort $ xs

据说以线性时间运行。我不明白为什么，因为您仍然必须分割每个子列表，直到到达单例/空列表，然后合并这些列表以保证返回列表的第一个元素是所有列表中最小的。我缺少什么？

Answer 1

但惰性仍然会影响 min xs = head 等定义。合并排序 $ xs. 在以这种方式查找最小元素时，只会执行元素之间必要数量的比较（对整个列表进行完全排序所需的 O(n) aot O(nlogn) 比较）。

你是对的，它的时间复杂度为O(n log(n))，但是如果你仔细阅读上面的段落，你会发现它正在谈论比较的数量。只会执行O(n)merge次比较，因为每个应用程序只需生成一个元素，因此它只需比较其参数的前两个元素。因此，您可以在递归的叶子处进行n/2比较，加上上一级的n/4比较，然后是n/4，...一直到递归的顶层。如果你计算出来，你会得到n-1次比较。