Следует за функцией Фибоначчи O (n) в Haskell

Как я узнал в SICP, сложность рекурсии дерева растет экспоненциально с увеличением n. Если бы в Haskell я написал вроде,

fib n | n <= 1 = n
      | otherwise = fib (n-1) + fib (n-2)

Верно ли, что, поскольку Haskell ленив, он вычисляет fib 1, _3 _... все один раз, поэтому сложность линейна с n?


lazy-evaluation big-o haskell fibonacci
person Xiaojun Chen    schedule 01.09.2016    source источник
comment
Возможный дубликат мемоизации в Haskell?   -  person Alec    schedule 01.09.2016
comment
Нет, Haskell не мемоизирует функции. Посмотрите что-нибудь вроде этого. Обратите внимание, что дополнительные сложности для мемоизации также возникают из-за полиморфного кода (этот вопрос в некотором роде актуален)   -  person Alec    schedule 01.09.2016
comment
Если вам нужна эта функция, вы должны использовать возведение матриц в степень возведением в квадрат. Это значительно быстрее, чем было бы линейное время, даже если бы вы его достигли.   -  person dfeuer    schedule 01.09.2016
comment
@dfeuer Технически это все еще O (n). Конечно, выполнение O (log n) умножений + сложений, вероятно, имеет меньшие константы, чем наивное решение с n сложениями, но оба выполняют O (n) битовых операций.   -  person Bakuriu    schedule 01.09.2016
comment
@dfeuer Вы имеете в виду упражнение 1.19 SICP   -  person Xiaojun Chen    schedule 01.09.2016
comment
@Bakuriu, по этому стандарту подход со списками даже не линейный, не так ли?   -  person dfeuer    schedule 01.09.2016
comment
@Bakuriu, также, ваше утверждение продолжает оставаться в силе, если используются чрезвычайно причудливые алгоритмы умножения (например, с преобразованием Фурье)?   -  person dfeuer    schedule 01.09.2016
comment
Передо мной нет SICP, Сяоцзюнь Чен, поэтому я не знаю.   -  person dfeuer    schedule 01.09.2016
comment
@dfeuer Число битов в числах Фибоначчи равно O (n) (они растут экспоненциально), что довольно точно в отношении сложности нижней границы для их вычисления, это была моя точка зрения.   -  person Bakuriu    schedule 01.09.2016
comment
@Bakuriu, да, я забыл, как быстро они бегут. Вы уверены, что наивный подход к n добавлению - O (n)?   -  person dfeuer    schedule 01.09.2016

Ответы (1)


arrow_upward
3
arrow_downward

Debug.Trace может указать количество вызовов fib:

import Debug.Trace

fib :: Int -> Int
fib n = trace "CALL" $ case n of
  0 -> 0
  1 -> 1
  _ -> fib (n-1) + fib (n-2)

Для fib 5 он выводит CALL 15 раз, поэтому это не O (n).

person V. Semeria    schedule 01.09.2016