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)

我知道我的问题是微不足道的。请把我当作一个新手，尝试学习 Big-O 表示法。

标签： algorithmtime-complexitybig-o

Answer 1

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

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