java - 如何估计第 n 个元素的斐波那契递归算法的时间？

Question

如何估计第 N 个斐波那契元素的以下算法的完成时间？

private static double fib(double nth){

        if (nth <= 2) return 1;
        else return fib(nth - 1) + fib(nth - 2);
    }

Answer 1

该算法的确切时间复杂度是……O(F(n))其中 F(N) 是第 n 个斐波那契数。为什么？请参阅下面的说明。

让我们通过归纳来证明它。显然它适用于基本情况（一切都是常数）。为什么它对 F(N) 成立？让我们将算法复杂度函数表示为 T(N)。然后T(N) = T(N-2) + T(N-1)，因为您进行了 2 次递归调用 - 一个参数减 1，一个减 2。而这个时间复杂度正是 Fibonacci 序列。

F(N)您可以做出的最佳估计也是如此，但您也可以说这是或者O(2^n)更准确地说是O(phi^n)where phi = (1 + sqrt(5)) / 2 ~= 1.61。为什么？因为第 n 个斐波那契数几乎等于phi ^ n.

这个界限使你的算法成为非多项式的，并且对于大于周围的数字非常慢30。你应该考虑其他好的算法——有许多已知的对数算法可以解决这个问题。