algorithm - 理解大 O 符号 O(2^N)

Question

我试图理解以下用于计算斐波那契数列的递归函数如何属于符号 O(2^N)。

int fibo(int num)
{
    if (num <= 1) return num;
    return fibonacci(num - 2) + fibonacci(num - 1);
}

例如，如果我们考虑寻找数字“5”的斐波那契数列，则 fibo 方法将被调用 15 次。我们怎么说它属于 O(2^N) 的符号？

                             fibo(5)
                        --------------------
                        /                  \
                  fibo(3)                   fibo(4)
                ------------              -------------  
                  /       \               /           \
            fibo(2)        fibo(1)   fibo(3)           fib0o(2)
      ----------------             ----------          -------------
       /            \              /        \           /         \
   fibo(1)          fibo(1)  fibo(2)        fibo(1)  fibo(1)      fibo(0)
                            ---------
                            /       \
                       fibo(1)       fibo(0)

我知道我的问题很简单。请将我视为新手，尝试学习大 O 表示法。

Answer 1

Big Oh 为您提供了算法运行时间的上限。那是，您必须阅读 O(2^n) 中的 fib(n) 以说明您的算法最多执行 2^n 步以返回结果。有时，上限不是那么精确(就是这种情况)。你也可以说 fib 在 O(n!) 中，这是另一个上限(一个非常糟糕的上限)。

为了说明算法的精确运行时间，您必须使用 Theta 表示法，在本例中 fib 是 Theta(Phi^n)，其中 Phi 是黄金比例。您可以通过归纳法证明这一点。