Haskell: tête. mergeSort (pour l'élément min) en temps linéaire?

Question

Dans le HaskellWiki https://wiki.haskell.org/Performance/Laziness ils introduisent la fonction de fusion de tri comme non paresseux

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 

depuis que vous avez à cliver récursive la liste

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 

puis, en remontant les couches de réduction, fusion celles-ci. Un fusion-tri s'exécute donc en n (log n) temps. Mais la composition

min xs = head . merge_sort $ xs 

fonctionne supposément en temps linéaire. Je ne vois pas pourquoi, car vous devez encore cliver chaque sous-liste jusqu'à ce que vous arriviez à la liste singleton/vide, puis fusionnez-les pour garantir que le premier élément de la liste retournée est le plus petit de tous. Qu'est-ce que je rate?

Answer 1

Mais lazyness entre toujours en jeu avec les définitions comme min xs = head. merge_sort $ xs. Dans la recherche de l'élément minimal de cette façon, seule la quantité nécessaire de comparaisons entre les éléments sera effectuée (O (n) a.o.t. O (nlogn) comparaisons nécessaires pour trier entièrement la liste entière).

Vous avez raison, il aura une complexité temporelle de O (n log (n)), si vous lisez le paragraphe ci-dessus vous soigneusement voir, qu'il parle du montant des comparaisons. Seules les comparaisons O (n) seront effectuées, car chaque application merge ne doit produire qu'un seul élément, elle n'a donc qu'à comparer les deux premiers éléments de ses arguments. Ainsi, vous obtenez n/2 comparaisons au niveau des feuilles de la récursion, plus n/4 un niveau supérieur, puis n/4, ... tout le chemin jusqu'au haut niveau de la récursion. Si vous travaillez, vous obtenez des comparaisons n-1.