斐波那契算法的分析 [英] analysis of fibonacci algorithm

问题描述

我正在阅读一个纤维球菌编号程序的分析，如下所示。提到这种实现方式效率低下。确实，对Fn进行递归调用的次数为F（n + 1）。

I am reading an analysis of a fibanocci number program, shown below. It is mentioned that this implementation is inefficient. Indeed, the number of recursive calls to compute Fn is F(n+1).

我的问题是：对Fn进行递归调用的次数为F （n + 1）是什么意思？

My question is: what does "the number of recursive calls to compute Fn is F(n+1)" mean?

int F(int i)
{ 
  if (i < 1) return 0;
  if (i == 1) return 1;
  return F(i-1) + F(i-2);
}

推荐答案

用于计算斐波那契的幼稚实现数字需要F（n + 1）个递归调用来计算数字F（n）;也就是说，要计算f（10）= 55，您需要进行89个递归调用，而89是F（11）。

The naive implementation to compute fibonacci numbers takes F(n+1) recursive calls to compute the number F(n); i.e. to compute f(10)=55 you need 89 recursive calls, and 89 is F(11).

这篇关于斐波那契算法的分析的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！