如何估计第N个斐波那契元素后续算法的完成时间？
private static double fib(double nth){
if (nth <= 2) return 1;
else return fib(nth - 1) + fib(nth - 2);
}
该算法的确切时间复杂度是...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)位置phi = (1 + sqrt(5)) / 2 ~= 1.61。为什么？因为第n个斐波那契数几乎等于phi ^ n。
此界限使您的算法成为非多项式算法，并且对于大于周围的数字而言，运算速度非常慢30。您应该考虑其他好的算法-有许多针对此问题的对数算法。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句