我试图比较这两个函数,看看哪个算法最好。我一直在研究 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]