动态规划斐波那契算法 [英] Dynamic Programming Fibonacci algorithm

问题描述

我正在研究一种计算斐波那契数的算法，并为其获取了伪代码，但是我无法弄清楚运行需要多少时间.我认为它的运行时间为O(n)，但不是很确定.这是代码:

I'm working on an algorithm to calculate a Fibonacci number and got the pseudo code for it but I can't figure out how much time it takes to run. I think it runs at O(n) but not quite sure. Here is the code:

Algorithm Fast-Fibonacci(n)
Let fib[0] and fib[1] be 1.
for each i from 2 to n, do:
    Let fib[i] be fib[i - 2] + fib[i - 1].
end of loop
return fib[n].

感谢您的帮助.

推荐答案

您正确地认为这需要O(n)，因为您只是从2到n依次计数以填充数组.如果您要对i-1和i-2中的每个数字进行某种形式的查找，这可能会增加复杂性，但是按照编写方式，您将为每个这些值调用一个直接地址.

You are correct that this takes O(n) as you are just counting sequentially from 2 to n to fill your array. If you were doing some sort of lookup for each of the i-1 and i-2 numbers, that could increase complexity, but the way you have written it, you are calling a direct address for each of those values.

这篇关于动态规划斐波那契算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！