List.fold和foldBack的渐近时间复杂度

Question

我试图理解这两个函数的时间复杂度.我试过试验这两个,这就是我想出来的

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])

现在在我看来它们都是线性的,因为它需要相同的计算量来实现相同的结果.我是正确还是有些东西我错过了？

Answer 1

如果每个内部操作是Θ(1),List.fold并且List.foldBack是O(n),其中n是列表的长度.

但是,要估计渐近时间复杂度,您需要依赖Θ(1)运算.在你的例子中,事情有点微妙.

假设您需要连接n每个列表中包含m元素的列表.由于@是O(n)左操作数的长度,我们有以下复杂性foldBack:

  m + ... + m // n occurences of m
= O(m*n)

和那个fold:

  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输入列表的大小是二次的.

值得注意的是,它@是关联的(a @(b @ c)=(a @ b)@ c); 因此,结果是相同的用于fold和foldBack在这种情况下.

实际上,如果内部运算符是非关联的,我们需要通过使用fold或选择正确的顺序foldBack.并且List.foldBack在F#中通过将列表转换为数组来进行尾递归; 这个操作也有一些开销.