f# - F# Flatten 関数の効率比較

Question

これら 2 つの関数を比較して、どちらが最適なアルゴリズムを持っているかを確認しようとしています。私は n の複雑さの順序を見てきました。数学的にそれに到達する方法はわかりませんが (これは残念です)、順序を推測できる場合があります。アルゴリズムが他のアルゴリズムよりも優れているかどうかを知るには、漸近時間、複雑さ、および実験的にそれらを調べる必要があると思います。

let flatten1 xs = List.fold (@) [] xs

let flatten2 xs = List.foldBack (@) xs []

私は F##time機能を使用しましたが、これが得られたものです。

Real: 00:00:00.001, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0
val it : int list =
  [1; 2; 3; 5; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16; 17; 18; 19;
   20; 5; 4; 5; 6]
>
Real: 00:00:00.001, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0
val it : int list =
  [1; 2; 3; 5; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16; 17; 18; 19;
   20; 5; 4; 5; 6]