斐波那契数列。时间复杂度

Question

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

所以这段代码的Big-O Notation是O(2^n)

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

即使我运行它使用 6 ，函数也会被调用 25 次在这张图片中看到：

Fibonacci 不应该是 64 因为 O(2^6) = 64 吗？

Answer 1

这里的逻辑有几个问题：

大 O 符号仅给出渐近上界，而不是紧界，这就是 big Theta 的用途。
Fibonacci 实际上是 Theta(phi^n)，如果您正在寻找更紧的边界（其中 phi 是 "golden ration"，phi ~= 1.618。
在谈论渐近符号时，谈论小数并忽略常量没有多大意义 - 因为它们因渐近复杂性而被省略（虽然这里不是这种情况）。

在这里，问题是斐波那契数确实是 O(2^n)，但这个界限并不严格，因此实际调用次数将低于估计次数（对于足够大的 n, 以后).

斐波那契数列。时间复杂度

Fibonacci sequence. Time Complexity

recursion

fibonacci

time-complexity