斐波那契函数执行的算术运算数

Niamh Akerman 发表于 Dev

尼姆·阿克曼（Niamh Akerman）

对于这个问题，我们给了函数f，它以标准方式计算第n个斐波那契数：

f(n)
 {
  if(n == 0)
   return 0;
  if(n == 1)
   return 1;
  else return f(n-1) + f(n-2);
 }

然后，我要负责计算函数在输入n上执行的算术运算次数。我知道每个对f的调用都会执行3个操作（2个减，1个加法），然后尝试通过扩展该函数尝试找到某种递归关系，然后算出要完成的算术运算数来找到它。但是后来我陷入困境，因为这不是正确的答案。

正确的答案是f对输入n进行3f（n + 1）-3个算术运算。请有人可以向我解释一下吗？这很重要，因为以后我们被要求以此为起点来查找时间复杂度。

非常感谢Niamh

香卡

您算法的时间复杂度接近2 ^（n）。因此它是O（2 ^ n）这是一个示例，说明如果n = 6时算法将如何求解

斐波那契的工作

你的算法做到了T(n) = T(n-1) + T(n-2) + O(1)。

T（n-1）= T（n-2）+ T（n-3）+ O（1）

T（n-2）= T（n-3）+ T（n-4）+ O（1）

。。。

T（2）= T（1）+ T（0）+ O（1）

看一下斐波那契时间的复杂性

T（n）= T（n-1）+ T（n-2）+ O（1）等于

T（n）= O（2 ^（n-1））+ O（2 ^（n-2））+ O（1）= O（2 ^ n）

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。

编辑于2021-02-16

我来说两句

0条评论

登录后参与评论

上一篇：iOS，LaunchImage Apple Watch的大小和名称

来自分类Dev