漸近時間複雜度和折返

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.foldList.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是輸入列表大小的二次方。

這是值得說明的是@是締合（一個@（B @ C）=（A @ B）@ C）;因此，在這種情況下，結果與fold和foldBack相同。

實際上，如果內部操作符是非關聯的，我們需要使用fold或foldBack來選擇正確的順序。通過將列表轉換爲數組，將F＃中的List.foldBack做成尾遞歸;這項操作也有一些開銷。

Answer 2

在一個天真的實現FoldBack是O(n^2)，你需要保持遍歷列表。在F＃編譯器實際上創建了一個臨時數組，並反轉，然後調用Fold，所以時間複雜性（以O換算）O(n)兩個，雖然Fold將由恆定量

Answer 3

的List.fold和List.foldBack功能都是T（Ñ）調用它們的功能參數，其中Ñ是列表的長度。但是，您正在向它們傳遞不是T（1）而是T（m）的函數m是第一個參數列表的長度。

特別地，這樣的：

(((([]@[1])@[2])@[3])@[4]) 

是T（ñ²），因爲[1]@[2]是一個操作，然後[1;2]@[3]是兩個操作，然後[1;2;3]@[4]爲三多個操作。