Ruby Fibonacci算法
以下是我编写的用于计算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）。 任何人都知道为什么会这样吗？
天真的斐波纳契进行了大量的重复计算 – 在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
正如其他人所指出的那样，你的实现的运行时间在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
由于您使用的递归，您的程序具有指数运行时。
仅扩展几个级别的递归调用以显示原因：
fib(14) = fib(13) + fib(12) = (fib(12) + fib(11)) + (fib(11) + fib (10)) = (((fib(11) + fib(10)) + (fib(10) + fib(9))) (((fib(10) + fib(9)) + (fib(9) + fib(8))) = ... //a ton more calls
可怕的运行时可能会导致程序挂起，因为将fib(n)增加1表示您有一个TON更多的递归调用
凯文L解释说，你的程序溢出了。
相反，你可以使用这样的迭代算法：
def fib (n) return 0 if n == 0 x = 0 y = 1 (1..n).each do z = (x + y) x = y y = z end return y end (0..14).map { |n| fib(n) } # [0, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610]
我尝试比较两个斐波纳契方法在repl.it上的运行时间
require 'benchmark' def fib_memo(n, memo = {}) if n == 0 || n == 1 return n end memo[n] ||= fib_memo(n-1, memo) + fib_memo(n-2, memo) end def fib_naive(n) if n == 0 || n == 1 return n end fib_naive(n-1) + fib_naive(n-2) end def time(&block) puts Benchmark.measure(&block) end time {fib_memo(14)} time {fib_naive(14)}
产量
0.000000 0.000000 0.000000 ( 0.000008) 0.000000 0.000000 0.000000 ( 0.000099)
如您所见，运行时完全不同。 正如@Uri Agassi建议的那样，使用memoization。 这个概念在这里解释得很好https://stackoverflow.com/a/1988826/5256509