runtime - 为什么斐波那契的运行时间是 θ(1.6^N)？

Question

为什么运行时间更接近 O(1.6^N) 而不是 O(2^N)？我认为这与调用堆栈有关，但我还是有点不清楚。

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

Answer 1

对于初学者，请记住大 O 表示法始终提供上限。也就是说，如果一个函数是 O(n)，它也是 O(n²), O(n³), O(2ⁿ), 等等。所以从这个意义上说，如果你说运行时间是 O(2ⁿ)，你并没有错。你只是没有严格的限制。

要查看 Θ(φⁿ) 的紧界从何而来，可能有助于查看在评估 Fibonacci(n) 时最终进行了多少次递归调用。 .注意

• Fibonacci(0)需要打一个电话，打给Fibonacci(0) .
• Fibonacci(1)需要打一个电话，打给Fibonacci(1) .
• Fibonacci(2)需要三个电话:一个到Fibonacci(2) , 每一个到 Fibonacci(0)和 Fibonacci(1) .
• Fibonacci(3)需要五个电话:一个到Fibonacci(3) , 然后是通过调用 Fibonacci(2) 生成的三个调用和通过调用 Fibonacci(1) 生成的一个调用.
• Fibonacci(4)需要九个电话:一个到Fibonacci(4) , 然后五个从调用 Fibonacci(3)三个来自 Fibonacci(2) 的电话.

更一般地说，模式似乎是如果您正在调用 Fibonacci(n)对于某些 n ≥ 2，调用次数为 1(对于调用本身)，加上计算 Fibonacci(n-1) 所需的调用次数和 Fibonacci(n-2) .如果我们让 L_n 表示调用的次数，这意味着我们有那个

• L₀ = L₁ = 1
• L_n+2 = 1 + L_n + L_n+1。

所以现在的问题是这个序列增长的速度有多快。评估前几个术语给我们

1, 1, 3, 5, 9, 15, 25, 41, ...

肯定会越来越大，但不清楚到底有多大。

您可能会在这里注意到 L_n 有点像斐波那契数列。也就是说，它是根据前两项的总和定义的，但它有一个额外的 +1 项。所以也许我们可能想看看 L_n 和 F_n 之间的区别，因为这可能会向我们展示 L 级数增长的“快”程度。您可能会注意到 L 系列的前两个值是 1、1，而斐波那契系列的前两个值是 0、1，因此我们将移动一个项以使事情排列得更好一些:

L(n)     1   1   3   5   9  15  25  41
F(n+1)   1   1   2   3   5   8  13  21
Diff:    0   0   1   2   4   7  12  20

等等，等一下。如果我们将差的每一项都加一，会发生什么情况？这给了我们

L(n)     1   1   3   5   9  15  25  41
F(n+1)   1   1   2   3   5   8  13  21
Diff+1   1   1   2   3   5   8  13  21

哇哦!看起来像 L_n - F_n+1 + 1 = F_n+1。重新排列，我们看到

L_n = 2F_n+1 - 1.

哇!所以 Fibonacci 递归函数的实际调用次数与返回的实际值密切相关。所以我们可以说斐波那契函数的运行时间是 Θ(F_n+1)，我们是对的。

但现在的问题是 φ 的来源。有一个可爱的数学结果叫做 Binet's formula即 F_n = Θ(φⁿ)。有很多方法可以证明这一点，但它们本质上都归结为观察结果

1. 斐波那契数似乎呈指数级快速增长；
2. 如果它们以 x 为底呈指数增长，则 F_n+2 = F_n + F_n+1 可以重写作为 x² = x + 1;和
3. φ 是 x² = x + 1 的解。

由此可见，既然斐波那契的运行时间是Θ(F_n+1)，那么运行时间也是Θ(φⁿ⁺¹) = Θ(φⁿ).