Haskell: 头。在线性时间内合并排序（对于最小元素）？

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

应该以线性时间运行。我不明白为什么，因为您仍然必须切割每个子列表，直到到达 singleton/empty 列表，然后合并它们以保证返回列表的第一个元素是所有元素中最小的。我错过了什么？

Answer 1

But lazyness still comes into play with the definitions like min xs = head . merge_sort $ xs. In finding the minimal element this way only the necessary amount of comparisons between elements will be performed (O(n) a.o.t. O(nlogn) comparisons needed to fully sort the whole list).

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

Haskell: 头。在线性时间内合并排序（对于最小元素）？

Haskell: head . mergeSort (for min element) in linear time?

sorting

mergesort

haskell

lazy-evaluation