算法

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)是多次计算的。

您可以在算法中添加回忆录，以使其速度更快：

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 )运行时间和存储(在堆栈上)

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

Answer 3

由于所使用的递归，您的程序具有exponential运行时。

只扩展几个级别的递归调用，以说明原因：

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意味着您有大量的递归调用。