big-o - Big O Notation - Fibonnaci - 破解编码面试示例 14，第 53 页

Question

我正在阅读“Cracking the Coding Interview”一书，第六章 Big(O)。在第 53 页，作者展示了这段代码并问：它的时间复杂度是多少？

    void allFib(int n) {
        for (int i = 0; i < n; i++) {
            System.out.println(i + ": " + fib(i));
        }
    }

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

他说这不是 O(n * 2^n) 而是 O(2^n) 因为：

• fib(1) --> 2^1 步
• fib(2) --> 2^2 步
• fib(3) --> 2^3 步
• ...
• fib(n) --> 2^n 步

因此，总工作量为 2^1 + 2^2 + 2^3 + ... + 2^n = 2^(n+1) = O(2^n)。

我的问题是：为什么 fib(2) = 4 步？在我看来，它是 5：fib(2) = 2 步（前两个 if 语句）+ fib(1) + fib(0) = 2 + 2 + 1 = 5。

标签： big-o

Answer 1

如果你过分关注细节，你会迷失方向。您已经知道 fib(n) 需要 O(2^n) 时间。例如，如果我们调用值为 5 的 allFib()，for 循环将调用值为 0 到 4 的 fib()，这意味着要获得总运行时间，我们必须添加 fib(0)+fib( 1)+...+fib(4)。

知道 fib(n) 的运行时间需要 O(2^n) 时间，将 n 替换为当前的 for 循环索引以获得运行时间。

• fib(0) - 2^0
• 纤维（1） - 2^1
• 纤维（2） - 2^2
• 纤维（3） - 2^3
• 纤维（4） - 2^4

然后添加 (2^0)+(2^1)+(2^2)+(2^3)+(2^4)+...(2^n) = 2^(n+1) = O (2^n)