为什么计算斐波纳契数需要很长时间? [英] Why it takes a long time to compute Fibonacci number?

问题描述

几天前，我开始学习Ocaml.我试图制作一个斐波那契数字的程序:

I started learning Ocaml a few days ago. I tried to make a program of fibonaaci numbers:

  let rec fib a=
      if a=1||a=2 then 1 else fib(a-1)+fib(a-2);;

此代码不是最佳代码，因为我不知道如何处理异常情况.但是现在，如果我尝试计算fib 50或fib 100，则计算机需要花费很长时间进行评估.我想知道为什么，因为Ocaml应该非常快，并且将数字加起来显然是线性的时间任务.如果我将此代码粘贴到"Try Ocaml"( http://try.ocamlpro.com/)中，则执行fib 50时整个网站冻结.

This code is not optimal as I do not know how to deal with exception cases. But for now, if I try to compute fib 50 or fib 100, then the computer takes a long time to evaluate. I am wondering why, because Ocaml is supposed to be very fast, and adding numbers up is obviously a linear time task. If I paste this code in "Try Ocaml" (http://try.ocamlpro.com/), then the whole website freezes when I execute fib 50.

很抱歉，如果问题的级别太低.

Sorry if the level of the question is too low.

推荐答案

因为这是不良递归用法的示例.应该禁止使用它作为优雅的递归示例，因为它确实非常不明智.机器.

Because this is the poster example for bad recursion usage. There should be a ban for using this as an example for the elegance of recursion, because it really is totally inelegant w.r.t. the machine.

对于每次呼叫fib的用户，您都会收获另外两个fib呼叫:

For every call to fib, you reap another two fib calls:

depth | call tree
------+------------------------------------------------------------------------
1     | fib-----+
      | |        \
2     | fib      fib
      | |   \    |   \
3     | fib  fib fib  fib
      | ....
4     | fib fib  fib  fib fib fib  fib  fib
      | ....
5     | fib fib  fib  fib fib fib  fib  fib 
      | fib fib  fib  fib fib fib  fib  fib
      | ....
6     | fib fib  fib  fib fib fib  fib  fib  
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib  
      | fib fib  fib  fib fib fib  fib  fib
      | ....
7     | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | ....
8     | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib          
      | ....
9     | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib
      | fib fib  fib  fib fib fib  fib  fib

...对于深度50，...

... and for depth 50, ...

 [562,949,950,000,000] × fib

...全部并行存在，每100万fib中大约有5.6亿个数据包.

... all existing in parallel, roughly 560 million packets of each a million fib.

您拥有的不是OCaml问题，而是计算/算法问题.对于不需要简单"递归的情况，斐波那契数是一个很好的例子.它看起来简单而优雅，但否认现实.

What you have is not an OCaml problem, but rather a computation/algorithm problem. Fibonacci numbers are a good example for a case where "simple" recursion is not desirable. It looks simple and elegant, but denies reality.

因此，将其实现为循环，您的问题将消失.

So, implement this as a loop instead and your problem will be gone.

这是一个指出计算复杂性的好问题( 大O符号 ).您的实现具有指数复杂度 O(2 ⁿ )，即，运行算法所需的时间随w.r.t呈指数增长.输入.一个求和循环将在 O(n)中运行，即解决问题所需的时间随w.r.t线性增长.输入.

This is a good question to point out computational complexity (Big O Notation). Your implementation has exponential complexity O(2ⁿ), i.e. the time required to run your algorithm grows exponentially w.r.t. to the input. A summing loop will run in O(n), i.e. the time required to solve the problem grows linearly w.r.t. to the input.

另请参见斐波那契系列的算法功能.

这篇关于为什么计算斐波纳契数需要很长时间?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！