斐波那契序列时间复杂度

Question

首先-是的，我知道有很多类似的问题，但我还是不明白。

所以这个代码的大O表示法是O(2^n)

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

即使我使用6运行它，函数也会被调用25，如图中所示：

由于O(2^6) = 64，斐波纳契不应该是64吗？

Answer 1

这里的逻辑很少有问题：

1. 大O表示法只是给出了上渐近界，而不是紧界，这就是大Theta的目的。
2. 斐波纳契实际上是Theta(phi^n)，如果你在寻找更紧的界限( phi是“黄金配给”，phi ~= 1.618 )。
3. 在讨论渐近表示法时，讨论低数和忽略常数是没有多大意义的--因为由于渐近复杂性而忽略了它们(但这里不是这样)。

在这里，问题是fibonacci确实是O(2^n)，但是这个界限并不紧，所以实际调用数将低于估计的调用数(对于足够大的n，以后)。