兩部分函數的時間複雜度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

這裏是如何通過每個長度3的n列出了兩個操作比較快&骯髒的片段：

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]多次...