0

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

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

更新

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

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

图形

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

4

5 回答 5

2

I would measure the time for a range of values and make table:

n | time

and then use matlab to fit to an exponential function.

keep in you mind that big-O notation is asymptotic and holds for a big number of elements.

enter image description here

you should try to write a c code for it. using inline function of the Fibonacci routine, and get the time in using ctime and store the values in two arraies. and after that analyzing the results using matlab or `python.

please post your outcomes...

于 2012-10-11T16:22:03.160 回答
2

很容易证明对函数的递归调用次数也遵循斐波那契数列。就像，如果F0=0并且F1=1是您的基本情况，则F2需要对函数进行 2 次调用，并且F3需要 3 次，依此类推。

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

于 2012-10-11T16:27:32.463 回答
2

显然，您正在运行用于计算斐波那契数列的朴素算法的实现。该算法具有指数复杂度： 斐波那契数列的计算复杂度(~ )。因此，您的程序在您的计算机上的运行时间大约为. 知道函数的结果（程序的运行时间），您应该能够计算常数，从而计算不同的近似时间。θ(1.6n)k*1.6nnkn

于 2012-10-11T16:29:34.867 回答
1

性能不仅取决于函数调用的数量和每次调用中的计算数量，还取决于您支付的费用 - 时间方面 - 由于递归算法而在堆栈上推入更多内容。我不知道堆栈推送是如何执行的，但它很可能在某个阈值之后开始更快地增加。所以，你必须找出这个阈值在哪里开始并适合（指数或其他）低于和高于（当你开始建立递归堆栈时，可能会有更多类似的性能损失）。

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

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

于 2012-10-11T22:10:03.460 回答
0

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

于 2012-10-11T20:52:05.387 回答