Асимптотическая сложность времени List.fold и foldBack - PullRequest
Новая
       63

Асимптотическая сложность времени List.fold и foldBack

2 голосов
/ 06 марта 2012

Я пытаюсь понять сложность времени для этих двух функций.Я попытался поэкспериментировать с обоими, и вот что я придумал 

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

Теперь мне кажется, что они оба линейны, поскольку для достижения одинакового результата требуется одинаковое количество вычислений.Я прав или есть что-то, чего мне не хватает?

Ответы [ 3 ]

5 голосов
/ 06 марта 2012

Если каждая внутренняя операция равна Θ (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 # делается хвост-рекурсивным путем преобразования списков в массивы; эта операция также имеет некоторые накладные расходы.

3 голосов
/ 06 марта 2012

Функции List.fold и List.foldBack - это T ( n ) вызовов их аргумента функции, где n - длина списка.Однако вы передаете им функцию (@), которая является не T (1), а T ( m ), где m - длина списка первого аргумента.

В частности, это: 

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

- это T ( n ²), поскольку [1]@[2] - это одна операция, а затем [1;2]@[3] - это еще две операции, а затем [1;2;3]@[4] - этоеще три операции.

1 голос
/ 06 марта 2012

В простой реализации FoldBack равно O(n^2), так как вам нужно продолжать обход списка. В F # компилятор фактически создает временный массив и переворачивает его, а затем вызывает Fold, поэтому временная сложность (в терминах O) составляет O(n) для обоих, хотя Fold будет немного быстрее на постоянную величину

...