3 
count = 0
def fibonacci(n):
    global count
    count = count + 1
    if not isinstance(n, int):
        print ('Invalid Input')
        return None

    if n < 0:
        print ('Invalid Input')
        return None

    if n == 0:
        return 0

    if n == 1:
        return 1

    fib = fibonacci(n-1) + fibonacci(n-2)
    return fib

fibonacci(8)
print(count)

我试图找出这个斐波那契程序的运行时间。任何人都可以帮助我解决相同的递归关系..

T(n) = T(n-1) + T(n-2)...从这里计算的运行时间是多少？

谢谢... ：）

4

4 回答 4

1

我假设你的意思是'斐波那契'，你说的是'阶乘'。

在每个级别，您都有两次调用fibonacci(). 这意味着您的运行时间将为 O(2^n)。您可以通过绘制递归树来看到这一点。

有关更好和更详细的解释，请参阅斐波那契数列的计算复杂性。

于 2011-07-10T08:04:34.660 回答
0

看看这个，尤其是 time.clock()。在函数调用之前和之后调用时钟，计算差值并得到经过的时间。

顺便说一句：为什么斐波那契的代码这么多？

def fib (n): return fib (n - 1) + fib (n - 2) if n > 1 else n
于 2011-07-10T08:05:02.197 回答
0

你可以看到wiki，但简单的观察正如你所写：

 T(n) < 2T(n-1) = 2 * 2 T(n-2) =.... = 2^(n-1)T(1) = 2^(n-1). So T(n) is in O(2^n).

事实上你应该解决x^2 = X + 1所以 x 将是phi1 = (1+sqrt(5))/2或者phi2 = (1-sqrt(5))/2结果是phi1 ^ n + phi2 ^n但是因为phi2对于大 n 来说小于 1 我们可以说它是T(n)=phi1^n.

编辑： *但是您可以编辑当前解决方案以花费 O(n) 运行时间（通过从第一个元素开始的 for 循环）。

于 2011-07-10T08:06:03.140 回答
0

运行时间是 2F(n+1) - 1 次调用，其中 n 是第 n 个斐波那契数。

这是一个快速的归纳证明：

作为基本情况，如果 n = 0 或 n = 1，那么我们只调用一次，并且 F(1) = F(2) = 1，我们有 2F(n+1) - 1 = 1。

对于归纳步​​骤，如果 n > 1，那么我们会进行尽可能多的调用来评估 n-1 和 n-2 上的函数。根据归纳假设，这需要 2F(n) - 1 + 2F(n-1) - 1 = 2F(n+1) - 2 次递归调用才能完成。但是，因为我们也计算当前函数调用，所以我们将其加一以获得 2F(n+1) - 1 根据需要。

请注意，2F(n+1) - 1 是第 n 个莱昂纳多数的表达式，其中

L(0) = L(1) = 1

L(n+2) = L(n) + L(n+1) + 1

正如 Saeed 指出的那样，它在 Θ(Φ n ) 处增长。但是，这个答案在数学上是准确的。

这更准确地说是您感兴趣的运行时，因为您需要考虑在每个递归调用本身中完成的工作。如果您省略 +1 项，您将得到斐波那契数列！

于 2011-07-10T09:00:50.413 回答