斐波那契数列时间复杂度

Question

老师，为什么斐波那契数列数列 递归写法的 时间复杂度是o(2^n) 还是有些不懂，您可否解释一下为什么是这个呢

Answer 1

双越 2022-07-13 08:41:09

其实很好理解。你看下课程里的这个图 

你可以试着自己画图，画三个 f(3)  f(4) f(5) 体会一下。你会发现，n 没增加一个数，图的规模就会增大一倍。即 f(5) 的图比 f(4) 图要大一倍。

这就是典型的 2^n 

Answer 2

双越 2022-07-09 14:13:55

首先，递归写法的斐波那契数列，一个数可能会重复计算很多次，这一点清楚吧？

• 提问者 三毛喜喜 #1

  这一点清楚的老师