Ruby Fibonacci算法

Question

以下是我编写的用于计算Fibonacci序列中的值的方法:

def fib(n)

    if n == 0
        return 0
    end
    if n == 1
        return 1
    end

    if n >= 2
        return fib(n-1) + (fib(n-2))
    end

end

它工作起来n = 14,但之后我得到一条消息说该程序花了太长时间才响应(我正在使用repl.it).任何人都知道为什么会这样吗？

Answer 1

天真的斐波纳契进行了大量的重复计算 - fib(14) fib(4)计算多次.

您可以为算法添加memoization以使其更快:

def fib(n, memo = {})
  if n == 0 || n == 1
    return n
  end
  memo[n] ||= fib(n-1, memo) + fib(n-2, memo)
end
fib 14
# => 377
fib 24
# => 46368
fib 124
# => 36726740705505779255899443

Answer 2

正如其他人所指出的那样,您的实现的运行时间呈指数级增长n.有更清洁的实现.

构造性[O(n)运行时间,O(1)存储]:

def fib(n)
  raise "fib not defined for negative numbers" if n < 0
  new, old = 1, 0
  n.times {new, old = new + old, new}
  old
end

记忆递归[O(n)运行时间,O(n)存储]:

def fib_memo(n, memo)
  memo[n] ||= fib_memo(n-1, memo) + fib_memo(n-2, memo)
end

def fib(n)
  raise "fib not defined for negative numbers" if n < 0
  fib_memo(n, [0, 1])
end

矩阵乘法的递归能力,使用平方减半的幂,当你只知道像1_000_000.fib [O(log n)运行时间和存储(堆栈)时真正的大因子时]:

def matrix_fib(n)
  if n == 1
    [0,1]
  else
    f = matrix_fib(n/2)
    c = f[0] * f[0] + f[1] * f[1]
    d = f[1] * (f[1] + 2 * f[0])
    n.even? ? [c,d] : [d,c+d]
  end
end

def fib(n)
  raise "fib not defined for negative numbers" if n < 0
  n.zero? ? n : matrix_fib(n)[1]
end