如何计算第n个斐波那契数的递归计算时间？

Question

如何知道当前机器上计算第n个斐波那契数需要多少时间？例如，在当前机器上，第 30 个元素的计算时间为 67 毫秒，第 40 个元素的计算时间为 554 毫秒。如何计算第99个元素的时间？

int fib(int n)
{
    if( n <= 2) 
        return 1
    else
        return fib(n-1) + fib(n-2)
}

---

更新

Fibonacci Nth vs ms（当前pc计算第n个斐波那契元素所花费的时间，时间以ms为单位） http://pastebin.com/PGnd54Hq

Matlab： 代码 http://pastebin.com/L9CH53Pf

如何找出第N个元素的时间？

Answer 1

我会测量一系列值的时间并制作表格：

n | time

然后使用

matlab

拟合指数函数。

• 在Matlab中通过数据点拟合指数曲线
• 指数拟合无需开始猜测
• 绘制指数曲线

请记住，大 O 表示法是渐近的并且适用于大量元素。

你应该尝试为它编写一个c代码。使用斐波那契例程的内联函数，并使用 ctime 获取时间并将值存储在两个数组中。然后使用

matlab

或 `python 分析结果。

请发布你的结果...

Answer 2

很容易证明函数的递归调用次数也遵循斐波那契数列。例如，如果

F0=0

和

F1=1

是您的基本情况，那么

F2

需要对该函数进行 2 次调用，而

F3

则需要 3 次，依此类推。

这证明了使用指数函数来适应您的时间，如 @0x90 建议的那样。

Answer 3

显然您正在运行一个用于计算斐波那契序列的朴素算法的实现。该算法具有指数复杂度：斐波那契数列的计算复杂度（~

θ(1.6

n

)

）。因此，程序在计算机上的运行时间大约为

k*1.6

n

。知道一个

n

的函数结果（程序的运行时间），您应该能够计算常数

k

，从而计算不同

n

的近似时间。

Answer 4

性能不仅取决于函数调用次数和每次调用内的计算次数，还取决于您因递归算法而在堆栈上推送更多内容所付出的时间代价。我不知道堆栈推送如何执行，但很可能在达到某个阈值后它开始更快地增加。因此，您必须找出这个阈值的启动位置并适合（指数或其他方式）下方和上方（并且当您开始构建递归堆栈时可能会有更多类似的性能损失）。

显然 - 尽管这不是问题 - 斐波那契数不应该以递归方式计算，即使这在数学上很优雅并且需要最简单的代码。

[添加/编辑] 我注意到您添加了时间测量图表。为了获得更好的洞察力，我建议垂直（倍）使用对数刻度。这将更清楚地显示整个图是否是“纯”指数的（对数图上的一条直线），或者它是否是一系列（不同的）指数或其他东西。指数部分可能从“某处”开始，或者变成另一个指数。

Answer 5

从列出的代码来看，每个调用都会进行 2 个调用。所以这个问题的简单答案是，每n个调用次数加倍，因此调用次数为2^(n-1)。例如，如果您正在计算 fib( 10 )，则调用次数将为 2^9 = 512。因此，如果需要 1 秒才能完成一次，则需要 512 秒才能完成所有对 fib( 10 的调用).

Answer 6

给定 (30, 67) 和 (40, 554) 的数字，您可以粗略地将指数曲线拟合到您的值，并得到 99 的大约 38.25 小时的估计值。