我试图理解这两个函数的时间复杂度。我已经尝试过两种方法，下面是我的想法
List.foldBack (@) [[1];[2];[3];[4]] [] => [1] @ List.foldBack (@) [[2];[3];[4]] []
=> [1] @ ([2] @ List.foldBack (@) [[3];[4]] [])
=> [1] @ ([2] @ ([3] @ List.foldBack (@) [4] []))
=> [1] @ ([2]@([3] @ ([4] @ List.foldBack[])))
=> [1]@([2]@([3]@([4]@([])))
=> [1; 2; 3; 4]
List.fold (@) [] [[1];[2];[3];[4]]
=> List.fold (@) (([],[1])@ [2]) [[3];[4]]
=> List.fold (@) ((([]@[1])@[2])@[3]) [[4]]
=> List.fold (@) (((([]@[1])@[2])@[3])@[4]) []
=> (((([]@[1])@[2])@[3])@[4])
在我看来，它们都是线性的，因为要达到同样的结果，需要同样的计算量。我是对的还是我遗漏了什么？
最佳答案
如果每个内部操作是Θ（1），List.fold和List.foldBack是O（n），其中n是列表的长度。
然而，为了估计渐近时间复杂度，需要依赖于（1）操作。在你的例子中，事情有点微妙。
假设您需要连接n列表，其中每个列表都有m元素。由于是左操作数长度的“cc>”，所以我们有复杂的@：
m + ... + m // n occurences of m
= O(m*n)
以及
O(n)： 0 + m + 2*m + ... + (n-1)*m // each time length of left operand increases by m
= m*n*(n-1)/2
= O(m*n^2)
因此，用您的简单方法使用
foldBack，fold是线性的，而@是输入列表大小的二次方。值得注意的是，
foldBack是关联的（a@（b@c）=（a@b）@c）；因此，在这种情况下，fold和@的结果是相同的。实际上，如果内部运算符是非关联的，我们需要使用
fold或foldBack来选择正确的顺序。F中的fold是通过将列表转换为数组而使尾部递归的；此操作也会产生一些开销。