O(2 ^ N)算法的示例

Question

我被告知过

O(2 ^ N)表示一种算法,其增长将随输入数据集中的每个附加元素加倍

有人能提供一个像这样的例子吗？

Answer 1

Fibonacci数的递归计算是O(2 ^N)算法的一个很好的例子(尽管O(2 ^N)不是它的紧束缚):

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