递归和非递归算法求解Fibonacci数列

对于Fibonacci数列

我们可以采用递归以及非递归的方法对其进行求解。

下面分别用两种方法求解，并分析算法的时间复杂度。

递归方法

伪代码：

# INPUT N
# OUTPUT Fibonacci数列的第N项数
Fibonacci(N):
    if N <= 1:
        return 1
    else
     return Fibonacci(N - 1) + Fibonacci(N - 2) 

正确性检测：

输入 时，

输入 时，

假设时 ，正确,

当 时， 正确。

So the correctness of Algorithm has been proved.

时间复杂度分析：

对于来说，每个问题被分成了两个子问题。每分割一次，问题的规模线性减少。

对于每个节点来说，每个节点对应算法执行一次操作的时间复杂度为。

二叉树的总层数为, 所以我们可以近似认为

下面给出具体分析：

Lower Bound

对于:

尾部常数 4 代表 四次常数操作 (1 comparison, 2 subtractions, 1 addition)

我们可以发现, 代入得：

所以lower bound我们说，

Upper Bound

我们认为 ， 因为

可得：

我们可以发现, 代入得：

所以对upper bound我们说，

综上，该算法时间复杂度

非递归方法

伪代码：

# INPUT N
# OUTPUT Fibonacci数列的第N项数
Fibonacci(N):
    A[0] = 1
    A[1] = 1
    for i = 2 to N - 1:
        A[i] = A[i - 1] + A[i - 2]
    return A[N - 1] 

时间复杂度分析：

首先，为A[0], A[1]赋值分别需要两个 的操作。

对于循环部分，时间复杂度为 。

所以

综上，迭代方法求解Fibonacci的时间复杂度为

最初发布在我的个人博客上。欢迎访问。