Fibonacci算法的时间复杂度
所以，我在Java中有一个递归方法来获得’第n个斐波纳契数 – 我唯一的问题是：时间复杂度是多少？ 我认为这是O（2 ^ n），但我可能弄错了？ （我知道迭代更好，但这是一个练习）
public int fibonacciRecursive(int n) { if(n == 1 || n == 2) return 1; else return fibonacciRecursive(n-2) + fibonacciRecursive(n-1); } 您的递归代码具有指数运行时。 但我不认为基数是2，但可能是黄金比例（约1.62）。 但当然O（1.62 ^ n）也自动为O（2 ^ n）。
可以递归计算运行时：
t(1)=1 t(2)=1 t(n)=t(n-1)+t(n-2)+1
这与斐波那契数字本身的递归定义非常相似。 递归方程中的+1可能与大n无关。 SI认为它的增长速度大约与纤维数一样快，并且随着黄金比例的增加呈指数增长。
您可以使用memoization加速它，即缓存已经计算的结果。 然后它就像迭代版本一样具有O（n）运行时。
您的迭代代码的运行时间为O（n）
你有一个简单的循环，每次迭代都有O（n）步和恒定时间。
你可以用它
计算F中的O（log n）
每个函数调用只进行一次加法，或返回1.基本情况只返回值1，因此加法的总数为fib（n）-1。 因此，函数调用的总数是2 * fib（n）-1，因此时间复杂度是Θ（fib（N））=Θ（phi ^ N），其由O（2 ^ N）界定。
O（2 ^ N）？ 我在这里只看到O（n）。
我想知道为什么你会继续计算和重新计算这些？ 只要记忆要求不会变得太可恶，不会缓存那些你是个好主意的人吗？
因为它们没有改变，所以如果速度对我很重要，我会生成一个表并进行查找。
很容易看到（并通过归纳certificate）对fibonacciRecursive的调用总数与返回的最终值完全相同。 这确实是输入数字的指数。