哈斯克爾：頭。 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 n）時間運行。但構圖

min xs = head . merge_sort $ xs 

據說在線性時間運行。我看不出爲什麼，因爲您仍然必須分解每個子列表，直到您到達單例列表/空列表，然後合併這些列表以確保返回列表的第一個元素是最小的。我錯過了什麼？

Answer 1

但懶惰仍然與min xs = head這樣的定義發揮作用。 merge_sort $ xs。通過這種方式找到最小元素只需執行元素之間所需的數量比較（O（n）a.o.t. O（nlogn）比較需要對整個列表進行完全排序）。

你是正確的，這將有Ø時間複雜度（N的log（n）），但是如果你看了上面的段落仔細，你會看到，它在談論比較的量。只有O（n）會執行比較，因爲每個merge應用程序只需生成一個元素，因此只需比較其參數的前兩個元素。所以你得到n/2比較在遞歸的葉子加n/4上一級，然後n/4，...一直到遞歸的頂層。如果你解決了這個問題，你可以得到n-1的比較結果。