Сложность времени O() двух функций двух частей

Question

Какова бы временная сложность этих двух алгоритмов?

let rec fol f a = function 
     | [] -> a 
     | x::xs -> fol f (f a x) xs;; 

let mergelist xs = List.fol (@) [] xs 

и

let rec folB f xs a = 
     match xs with 
     | [] -> a 
     | y::ys -> f y (folB f ys a);; 

let mergelist2 xs = List.folB (@) xs [] 

и как бы я быть в состоянии проверить это мой сам?

Если вернуть что-то вроде

mergelist [[1;2];[];[3];[4;5;6]];; 
    val it : int list = [1; 2; 3; 4; 5; 6] 

Answer 1

Вот быстрый & грязный кусок, как вы можете сравнить две операции с n списками длины 3 каждого:

let rec fol f a = function 
     | [] -> a 
     | x::xs -> fol f (f a x) xs;; 

let rec folB f xs a = 
     match xs with 
     | [] -> a 
     | y::ys -> f y (folB f ys a);; 

let compareThemFor n = 
    let testList = List.replicate n [1;2;3] 
    let count = ref 0 

    let myCons x xs = 
     incr count 
     x :: xs 

    let myApp ys = 
     List.foldBack myCons ys 

    let mergelist = fol myApp [] 
    mergelist testList |> ignore 
    let countA = !count 

    count := 0 
    let mergelist2 xs = folB myApp xs [] 
    mergelist2 testList |> ignore 
    let countB = !count 

    (countA, countB) 

и это то, что вы будут получены:

> compareThemFor 2;; 
val it : int * int = (3, 6) 
> compareThemFor 3;; 
val it : int * int = (9, 9) 
> compareThemFor 4;; 
val it : int * int = (18, 12) 
> compareThemFor 5;; 
val it : int * int = (30, 15) 
> compareThemFor 6;; 
val it : int * int = (45, 18) 

, поскольку вы можете видеть, что второе намного лучше, и я надеюсь, что приведенные выше комментарии помогут вам понять, почему.

Только в случае, если здесь есть версия n=3 для mergelist:

mergelist [[1;2;3];[3;4;5];[6;7;8]] 
{ second case in `fol` with `x=[1;2;3]` and `xs=[[3;4;5];[6;7;8]]` } 
= fol (@) ([] @ [1;2;3]) [[3;4;5];[6;7;8]] // one @ of 0 elements = 0 operations 
{ second case in `fol` with `x=[3;4;5]` and `xs=[[6;7;8]]` } 
= fol (@) ([1;2;3] @ [3;4;5]) [[6;7;8]] // one @ of 3 elements = 3 operations 
{ second case in `fol` with `x=[6;7;8]` and `xs=[]` } 
= fol (@) ([1;2;3;3;4;5] @ [6;7;8]) [] // one @ of 6 elements = 6 operations 
{ first case } 
= [1;2;3;3;4;5;6;7;8] // 0+3+(3+3)=9 Operations Total 

Обратите внимание, что вы предварять [1,2,3] несколько раз ...