哈斯克尔:头。mergeSort (用于最小元)在线性时间？

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 )时间内运行。但是这篇文章

min xs = head . merge_sort $ xs

据说是线性时间运行的。我不明白为什么，因为您仍然必须切割每个子列表，直到您到达单例/空列表，然后合并它们以保证返回列表的第一个元素是最小的。我遗漏了什么？

Answer 1

但是，像min = head这样的定义仍然起着作用。merge_sort $ xs.在以这种方式找到最小元素时，只需要在元素之间执行必要的比较(O(n) a.o.t )。O(nlogn)比较需要完全排序整个列表)。

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